Аскар, который учится писать буквы «ш» и «и», написал несколько букв, как на рисунке справа. Сколькими способами можно прочитать эти буквы, используя всю строку целиком?

На рисунке изображена последовательность букв, похожих на "ш" и "и". Нужно посчитать количество способов прочитать эту последовательность как комбинацию букв "ш" и "и", используя все символы.

Предположим, что каждый "зубец" соответствует букве "и", а три "зубца" - букве "ш". Посчитаем количество зубцов: их 8.

Возможные варианты:

• 2 буквы "ш" и 0 букв "и" (невозможно, так как 2*3 = 6 зубцов, а их 8)
• 1 буква "ш" и 5 букв "и" (3 + 5 = 8 зубцов)
• 0 букв "ш" и 8 букв "и" (0 + 8 = 8 зубцов)

Теперь посчитаем количество способов для каждого варианта:

• 1 "ш" и 5 "и". Нужно выбрать позицию для "ш" среди 6 позиций (1 "ш" + 5 "и" = 6 букв). Это можно сделать 6 способами.
• 0 "ш" и 8 "и". Есть только 1 способ.

Суммарное количество способов: 6 + 1 = 7.

Теперь другой способ решения:

Обозначим букву "и" как 1, а "ш" как 0.

Пусть a[i] - количество способов прочитать первые i зубцов.

a[0] = 1

a[i] = a[i-1] + a[i-3], если i >= 3

a[1] = a[0] = 1

a[2] = a[1] = 1

a[3] = a[2] + a[0] = 1 + 1 = 2

a[4] = a[3] + a[1] = 2 + 1 = 3

a[5] = a[4] + a[2] = 3 + 1 = 4

a[6] = a[5] + a[3] = 4 + 2 = 6

a[7] = a[6] + a[4] = 6 + 3 = 9

a[8] = a[7] + a[5] = 9 + 4 = 13

Ответ: 13