Question

55 БАЛЛОВ!!! В Тридесятом государстве всего 8 городов, каждые два из которых соединены прямой дорогой. Правитель этого государства решил модернизировать систему автодорог, связывающих города. Он пронумеровал города числами от 1 до 8 в порядке возрастания важности города (самый захолустный город получил номер 1, а столица – номер 8) и ввел одностороннее движение на части дорог, а все остальные дороги закрыл. Одностороннее движение таково: можно проехать от города с номером N до городов с номерами N + 1, N + 2 и N + 3 (если они есть). То есть, работают дороги 1-2, 1-3, 1-4, 2-3, 2-4, 2-5, 3-4, 3-5, 3-6, …, 5-6, 5-7, 5-8, 6-7, 6-8, 7-8. В обратном направлении по дорогам ехать нельзя, то есть, в частности, в город 1 по новым правилам доехать ни из какого города не получится. Сколькими способами теперь можно добраться от города с номером 1 до города с номером 7?

Answer 1

Построен граф по описаной системе. Значение на каждом ребре показывает сколько дорог к нему ведут - находится путем сумирования значений всех путей приведших к вершине
ответ 24

Answer 2

Для решения этой задачи мы можем использовать динамическое программирование. Давайте создадим массив ways, где ways[i] будет представлять количество способов добраться от города с номером 1 до города с номером i, используя новые правила одностороннего движения.

Из условия известно, что можно проехать от города с номером N до городов с номерами N + 1, N + 2 и N + 3 (если они есть). Мы начнем с города с номером 1 и будем двигаться по массиву ways от левого края к правому, заполняя его значения. Сначала установим ways[1] = 1, так как из города 1 можно доехать только до города 2. Затем будем итеративно заполнять остальные значения массива ways:

cssCopy code
ways[2] = ways[1] = 1
ways[3] = ways[1] + ways[2] = 2
ways[4] = ways[1] + ways[2] + ways[3] = 4
ways[5] = ways[2] + ways[3] + ways[4] = 7
ways[6] = ways[3] + ways[4] + ways[5] = 13
ways[7] = ways[4] + ways[5] + ways[6] = 24
ways[8] = ways[5] + ways[6] + ways[7] = 44

Таким образом, существует 24 способа добраться от города с номером 1 до города с номером 7, используя новые правила одностороннего движения.