У Жоры есть коробка конфет, в которой конфеты расположены прямоугольником 4 × 10 (4 строчки, 10 столбцов). Жора берёт по одной конфете, каждый раз выбирая из строки, в которой осталось максимальное количество конфет; если таких несколько — из любой из них. Сколькими способами Жора мог съесть первые 5 конфет? Порядок поедания важен.

Для решения этой задачи можно использовать динамическое программирование.

Пусть dp[i][j] - количество способов, которыми Жора мог съесть j конфет из первых i строк.

Инициализируем dp[0][0] = 1.

Далее, для каждого i от 1 до 4 и для каждого j от 1 до 5, будем пересчитывать dp[i][j] следующим образом:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Таким образом, после пересчета всех значений dp, ответом на задачу будет dp[4][5].

Вычислим все значения dp:

dp[0][0] = 1 dp[1][0] = 1, dp[1][1] = 1, dp[1][2] = 1, dp[1][3] = 1, dp[1][4] = 1, dp[1][5] = 1 dp[2][0] = 1, dp[2][1] = 2, dp[2][2] = 3, dp[2][3] = 4, dp[2][4] = 5, dp[2][5] = 6 dp[3][0] = 1, dp[3][1] = 3, dp[3][2] = 6, dp[3][3] = 10, dp[3][4] = 15, dp[3][5] = 21 dp[4][0] = 1, dp[4][1] = 4, dp[4][2] = 10, dp[4][3] = 20, dp[4][4] = 35, dp[4][5] = 56

Ответ: Жора мог съесть первые 5 конфет 56 способами.