Question

Мальчик Вася хочет сделать бутерброд. Для начинки он использует кусочки сыра и колбасы, которые кладет поверх друг друга. В его бутерброде должно быть 5 кусочков начинки. Вася считает бутерброд неправильным, если в начинке подряд лежат 2 кусочка сыра. Например, бутерброд КСКСК – является правильным, а ККССК – неправильный (К – колбаса, С – сыр). Найдите количество правильных бутербродов, по мнению Васи.

Answer 1

Ответ:

Думаю 7, но возможно больше.

Пошаговое объяснение:

Исходя из того, что сочетание КСКСК - правильное, то:

1. КСКСК

2. СКСКС

3. ККСКС

4. КСККС

5. СКСКС

6. СККСК

7. СКККС

Answer 2

Для нахождения количества правильных бутербродов, по мнению Васи, мы можем использовать динамическое программирование.

Предположим, что у нас есть два состояния, которые будем отслеживать при создании бутерброда:

1. Последний ингредиент - сыр (С).
2. Последний ингредиент - колбаса (К).

Создадим два массива для отслеживания количества правильных бутербродов, заканчивающихся сыром (dp_syr) и колбасой (dp_kolbasa). Начнем с базового случая:

dp_syr[0] = 0 (бутерброд без ингредиентов) dp_kolbasa[0] = 0 (бутерброд без ингредиентов)

Теперь будем строить массивы dp_syr и dp_kolbasa, итеративно добавляя ингредиенты:

1. Если мы добавляем сыр (С) к бутерброду, который заканчивается сыром, то dp_syr[i] = dp_syr[i-1] + dp_kolbasa[i-1] (мы можем добавить сыр к предыдущему бутерброду, который заканчивается колбасой).
2. Если мы добавляем колбасу (К) к бутерброду, который заканчивается сыром, то dp_kolbasa[i] = dp_syr[i-1] (мы не можем добавить колбасу к предыдущему бутерброду, который уже заканчивается сыром).
3. Если мы добавляем колбасу (К) к бутерброду, который заканчивается колбасой, то dp_kolbasa[i] = dp_kolbasa[i-1] + dp_syr[i-1] (мы можем добавить колбасу к предыдущему бутерброду, который заканчивается сыром, и создать новый бутерброд, который заканчивается колбасой).

Теперь мы можем начать построение массивов dp_syr и dp_kolbasa для каждой длины бутерброда от 1 до 5 (поскольку Вася хочет 5 кусочков начинки). В конечном итоге, суммируем значения из dp_syr[5] и dp_kolbasa[5], чтобы найти общее количество правильных бутербродов.

Давайте вычислим значения для каждой длины бутерброда:

dp_syr[1] = 0 dp_kolbasa[1] = 1

dp_syr[2] = 1 dp_kolbasa[2] = 0

dp_syr[3] = dp_syr[2] + dp_kolbasa[2] = 1 dp_kolbasa[3] = dp_syr[2] = 1

dp_syr[4] = dp_syr[3] + dp_kolbasa[3] = 2 dp_kolbasa[4] = dp_syr[3] + dp_kolbasa[3] = 2

dp_syr[5] = dp_syr[4] + dp_kolbasa[4] = 4 dp_kolbasa[5] = dp_syr[4] + dp_kolbasa[4] = 4

Теперь суммируем dp_syr[5] и dp_kolbasa[5]:

Общее количество правильных бутербродов = dp_syr[5] + dp_kolbasa[5] = 4 + 4 = 8

Итак, согласно мнению Васи, существует 8 правильных способов сделать бутерброд с 5 кусочками начинки.