Тапсырма 8 ЕГЭ по информатикаға: ФИПИ шешімдері қадамдық жауаптарымен

В алфавитном порядке буквы расположены так: А, Б, Р, Т, Ы. Буква Ы в искомом слове отсутствует.

Слово, начинающееся с АА, не подходит, так как содержит рядом стоящие буквы А. После первой буквы А минимально возможна буква Б.

Сопоставим буквам их порядковые нөмір, начиная с нуля: А = 0, Б = 1, З = 2, И = 3.

Позиции букв в слове ИЗБА имеют веса $4^3$, $4^2$, $4^1$ и $4^0$.$$3 \cdot 4^3 + 2 \cdot 4^2 + 1 \cdot 4^1 + 0 \cdot 4^0 = 192 + 32 + 4 = 228$$

Так как число делится на 5, его последняя цифра — 0 или 5. Условие о соседних цифрах означает, что чётность цифр должна чередоваться.

Если последняя цифра равна 0, шаблон чётности имеет вид нечётная–чётная–нечётная–чётная. Первую и третью цифры можно выбрать упорядоченно из пяти нечётных цифр: $5 \cdot 4$. Вторую цифру выбираем из четырёх ненулевых чётных цифр: $4$…

Обозначим через $F_{\max}(i,j)$ максимальную сумму, которую можно собрать при попадании в клетку $(i,j)$, а через $F_{\min}(i,j)$ — минимальную сумму.

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

Подходящее слово не может начинаться с Е, И или О. Минимальная возможная первая буква — Р.

До слов, начинающихся с Р, идут все слова с первыми буквами Е, И и О. Их количество равно:$$3 \cdot 6^5 = 23328$$

Сначала рассмотрим слова, в которых буква В не используется. На последней позиции можно поставить одну из двух согласных букв, а на остальные позиции — любую из четырёх букв.$$N_1 = 2 \cdot 4^5 = 2048$$

Теперь рассмотрим слова, в которых буква В встречается ровно один раз. Если В стоит на первой позиции, остальные позиции дают $2 \cdot 4^4$ вариантов. Если В стоит на одной из четырёх внутренних позиций, получаем $4 \cdot 2 \cdot 4^4$…$$N_2 = 2 \cdot 4^4 + 4 \cdot 2 \cdot 4^4 + 4^4 = 2304$$