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

Рассматриваем шестизначные жазбалар в шестеричной системе и фиксируем положение единственной цифры 2.

Для каждой позиции цифры 2 перебираем допустимые значения соседних разрядов: рядом с цифрой 2 могут стоять только чётные цифры, а остальные разряды заполняются цифрами, отличными от 2. Для первого разряда дополнительно исключается 0.

Без цифры 5 остаются чётные цифры $0, 2, 4, 6, 8$ — всего 5 цифр, и нечётные цифры $1, 3, 7, 9$ — всего 4 цифры.

Так как соседние цифры не могут иметь одинаковую чётность, возможны только два шаблона: ЧНЧНЧ или НЧНЧН.

Проверим цепочку ББДГ. Первая буква Б кіреді в множество А, Б, В, Г и является согласной.

Так как первая буква согласная, на втором месте также должна стоять согласная буква. Б — согласная.

В алфавитном порядке разрешённые буквы идут так: И, Р, С, Т, У, Ц. Всего возможны $6^5$ слов.

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

Если цифр $7$ нет, первая цифра выбирается 6 способами: $1$–$6$, а остальные четыре цифры — по 7 способов, так как цифра $7$ запрещена.$$N_0=6\cdot7^4=14406$$

Если ровно одна цифра равна $7$, она может стоять первой, либо на одной из четырёх оставшихся позиций.$$N_1=7^4+6\cdot4\cdot7^3=2401+8232=10633$$

Построим две таблицы динамического программирования: $max[i][j]$ — максимальная сумма при достижении клетки $(i,j)$, а $min[i][j]$ — минимальная сумма.

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

Алфавит содержит 5 букв: К, Л, Н, Т, Э. Слова упорядочены как записи в пятеричной системе счисления с цифрами от 0 до 4.$$К=0,\ Л=1,\ Н=2,\ Т=3,\ Э=4$$

В слове ККЛККН третья буква Л. Перед ней на этой позиции может стоять только К, поэтому перед нужной группой находятся слова с началом ККК. Таких слов $5^3=125$.$$5^3=125$$

В алфавитном порядке буква Е идёт перед буквой Л, поэтому сначала будут записаны все слова, начинающиеся с Е.

После первой буквы остаются три позиции. Каждую из них можно заполнить одной из пяти разрешённых букв.$$5^3 = 125$$

Первая цифра не может быть нечётной и не может быть нулём, поэтому для неё доступны цифры $2, 4, 6, 8$: всего 4 варианта.

Последняя цифра не может быть равна 1 или 8. Всего для неё доступно 7 цифр. Если цифра 3 не используется, остаётся 6 вариантов.

Буквы упорядочены так: А, В, О, Р, Т. Позиции букв слова ВОРОТА имеют номера $1, 2, 3, 4, 5$ соответственно, если считать с нуля.$$В\,О\,Р\,О\,Т\,А \rightarrow 1,2,3,2,4,0$$

До слова ВОРОТА находится указанное количество слов с меньшей буквой на каждой позиции.$$1\cdot5^5 + 2\cdot5^4 + 3\cdot5^3 + 2\cdot5^2 + 4\cdot5^1 + 0\cdot5^0 = 3125+1250+375+50+20=4820$$

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

Если в клетку можно прийти сверху или слева, максимум равен стоимости монеты в клетке плюс больший из соответствующих максимумов, а минимум — стоимости монеты плюс меньший из соответствующих минимумов.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1}),\quad m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$

Алфавитный порядок букв: А, М, Р, Т. Перед словами, начинающимися с Т, расположены все слова, начинающиеся с А, М или Р.

Для каждой фиксированной первой буквы оставшиеся три позиции можно заполнить любыми из төрт букв.$$4^3 = 64$$

Буквы в алфавитном порядке имеют номера: А — 0, К — 1, О — 2, Р — 3, С — 4, Т — 5. Всего используется система счисления с основанием 6.

Чтобы слово было последним, оно должно начинаться с максимально возможной буквы Т. Единственную букву С выгоднее поставить как можно правее; последняя позиция должна быть максимальной буквой Т. Получаем слово ТТТРТ.

Так как никакие две цифры одной чётности не стоят рядом, чётность цифр должна чередоваться. Возможны два типа последовательности: нечётная–чётная–нечётная–чётная–нечётная–чётная и чётная–нечётная–чётная–нечётная–чётная–нечётная.

Если число начинается с нечётной цифры, нечётные цифры можно выбрать и расставить на трёх позициях $5 \cdot 4 \cdot 3$ способами. Чётные цифры также выбираются и расставляются $5 \cdot 4 \cdot 3$ способами.$$N_1=(5\cdot4\cdot3)^2=3600$$

В алфавитном порядке сначала идут все слова, начинающиеся с буквы А.

После первой буквы остаются три позиции. Каждую из них можно заполнить одной из четырёх букв, поэтому количество слов, начинающихся с А, равно:$$4^3 = 64$$

Единственную гласную букву можно поставить на любую из 5 позиций, а выбрать её можно 2 способами: А или У.$$5 \cdot 2$$

На каждой из оставшихся 4 позиций может стоять одна из двух согласных букв: П или К.$$2^4$$

В шестнадцатеричной системе есть 8 чётных цифр ($0, 2, 4, 6, 8, A, C, E$) и 8 нечётных цифр ($1, 3, 5, 7, 9, B, D, F$). Чётность цифр должна чередоваться, поэтому возможны две схемы.

Если первой стоит чётная цифра, то она не может быть нулём: 7 вариантов. Затем выбираются нечётная цифра — 8 вариантов, чётная — 7 вариантов и нечётная — 7 вариантов.$$7 \cdot 8 \cdot 7 \cdot 7 = 2744$$

Перед словами, начинающимися с Р, находятся все слова, начинающиеся с К или М. Таких слов $2 \cdot 3^4$.$$2 \cdot 3^4 = 162$$

После первой буквы Р учитываем слова с меньшими вариантами второй и третьей букв: перед Р стоят К и М.$$2 \cdot 3^3 + 2 \cdot 3^2 = 54 + 18$$

Единственную букву К можно расположить на любой из алты позиций.$$6$$

На каждой из оставшихся пяти позиций независимо выбирается буква О или Т, поэтому число вариантов заполнения этих позиций равно:$$2^5$$

Единственная цифра 3 может находиться в одной из пяти позиций. Для каждой позиции учитываем ограничения на соседние цифры и запрет ведущего нуля.

В соседних позициях с цифрой 3 разрешены только цифры 0, 1, 2 и 4, а в остальных позициях используются цифры девятеричной системы, кроме 3.