Question

Мистер Фокс разрабатывает программу для робота-лунохода. Сегодня его роботу нужно добраться по прямой дороге длиной 24 фута от космодрома до базы, попутно забрав ценный предмет. Будем считать дорогу отрезком, в левом конце которого находится космодром, в правом конце – база, а ровно посередине – лежит ценный предмет. Мистер Фокс может давать роботу три команды: A – сместиться на 1 фут вправо, B – сместиться на 2 фута вправо, C – сместиться на 3 фута вправо. Набор из 24 фута команд A является удачным, так как приводит робота на базу (попутно он заберет ценный предмет, потому что остановится около него), а вот набор BCCBCBCCC удачным не является: робота на базу он приведет, но вот ценный предмет робот не заберет, поскольку не остановится около него. Сколько существует удачных наборов команд?

Answer 1

Все удачные наборы команд должны включать остановку на отметке 12 футов.
На отметку 1 фут робот может попасть с помощью одной команды A;
на отметку 2 фута - с помощью команд AA и B (всего 2 набора команд);
на отметку 3 фута - с помощью команд AAA, AB, BA и C (4 набора).
Так как за одну команду робот может переместиться на 1, 2 или 3 фута, то для подсчета количества наборов команд, позволяющих роботу попасть на отметки N > 3, можно использовать формулу
K(N) = K(N-1)+K(N-2)+K(N-3).
Напимер, на отметку 4 фута робот может попасть с отметок 3, 2 или 1 фут, следовательно, количество способов попасть на отметку 4 определяется как K(3)+K(2)+K(1).
K(4) = K(3)+K(2)+K(1) = 4+2+1 = 7
K(5) = K(4)+K(3)+K(2) = 7+4+2 = 13
K(6) = K(5)+K(4)+K(3) = 13+7+4 = 24
K(7) = K(6)+K(5)+K(4) = 24+13+7 = 44
K(8) = K(7)+K(6)+K(5) = 44+24+13 = 81
K(9) = K(8)+K(7)+K(6) = 81+44+24 = 149
K(10) = K(9)+K(8)+K(7) = 149+81+44 = 274
K(11) = K(10)+K(9)+K(8) = 274+149+81 = 504
K(12) = K(11)+K(10)+K(9) = 504+274+149 = 927
Так как вторая часть пути робота также имеет длину 12, то общее количество удачных наборов команд = 927*927 = 859 329

Answer 2

Для того чтобы рассчитать количество удачных наборов команд, нужно найти все возможные комбинации команд A, B и C, которые приведут робота на базу и захватят ценный предмет по пути.

Мы можем решить эту задачу с помощью динамического программирования. Для каждого возможного числа футов, которые осталось пройти до базы (от 0 до 24), мы будем подсчитывать количество удачных комбинаций.

Назовем массив dp, где dp[i] - количество удачных комбинаций для остатка в i футов до базы.

Таким образом, dp[0] будет равно 1, так как если осталось 0 футов до базы, значит, робот уже на базе, и у нас есть один удачный набор команд - ничего не делать.

Теперь рассмотрим остаток в 1 фут до базы. Чтобы добраться до этой точки, робот может использовать только одну команду A. Таким образом, dp[1] = dp[1-1] = dp[0] = 1.

Для остатка в 2 фута до базы (dp[2]) робот может использовать команду A дважды или команду B один раз. Таким образом, dp[2] = dp[2-1] + dp[2-2] = dp[1] + dp[0] = 1 + 1 = 2.

Точно так же, для остатка в 3 фута до базы (dp[3]) робот может использовать команду A трижды, команду A один раз и команду B один раз или команды B и C один раз каждую. Таким образом, dp[3] = dp[3-1] + dp[3-2] + dp[3-3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = 4.

Мы можем продолжить заполнение массива dp до dp[24], чтобы найти общее количество удачных наборов команд. Таким образом, dp[24] будет содержать ответ на задачу.

Вот заполненный массив dp:

dp[0] = 1 dp[1] = 1 dp[2] = 2 dp[3] = 4 dp[4] = 7 dp[5] = 13 dp[6] = 24 dp[7] = 44 dp[8] = 81 dp[9] = 149 dp[10] = 274 dp[11] = 504 dp[12] = 927 dp[13] = 1705 dp[14] = 3136 dp[15] = 5768 dp[16] = 10609 dp[17] = 19513 dp[18] = 35890 dp[19] = 66012 dp[20] = 121415 dp[21] = 223317 dp[22] = 410744 dp[23] = 755476 dp[24] = 1389537

Таким образом, существует 1 389 537 удачных наборов команд, которые приведут робота на базу и захватят ценный предмет по пути.