Задание 8 ЕГЭ по информатике: решения ФИПИ с ответами по шагам

Буквы имеют порядковые номера от 0 до 6: А, Ж, И, М, Н, У, Ч. Номер слова равен единице плюс его номер в семеричной системе. Поэтому чётность номера определяется последней буквой.

Номер слова будет чётным, если последняя буква имеет нечётный порядковый номер: Ж, М или У. Таким образом, последняя буква выбирается тремя способами.

В десятичной системе есть 5 чётных цифр ($0, 2, 4, 6, 8$) и 5 нечётных цифр ($1, 3, 5, 7, 9$). Из-за условия о соседних цифрах возможны только два шаблона чётности: Ч–Н–Ч–Н и Н–Ч–Н–Ч.

Для шаблона Ч–Н–Ч–Н первую чётную цифру можно выбрать 4 способами, так как ноль на первом месте невозможен. Вторую нечётную цифру выбираем 5 способами, третью чётную — 4 способами, четвёртую нечётную — 4 способами.$$4 \cdot 5 \cdot 4 \cdot 4 = 320$$

Буквам соответствуют цифры пятеричной системы счисления в порядке списка: К — 0, О — 1, С — 2, У — 3, Ф — 4.

Слово должно содержать ровно две буквы У и не содержать Ф. Последним в алфавитном порядке будет слово УУССС: две наиболее старшие допустимые буквы У ставятся в первые позиции, остальные позиции занимают С.$$УУССС_5 = 3 \cdot 5^4 + 3 \cdot 5^3 + 2 \cdot 5^2 + 2 \cdot 5 + 2$$

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

Если в клетку можно попасть из соседней клетки сверху, переход разрешён только при отсутствии стены между ними. Аналогично проверяется переход слева.

Число, делящееся на 5, должно оканчиваться цифрой 0 или 5. Из-за чередования чётных и нечётных цифр рассмотрим эти случаи отдельно.

Если последняя цифра равна 0, последовательность чётности имеет вид «нечётная, чётная, нечётная, чётная, чётная» с учётом фиксированной последней цифры и чередования на первых позициях. На первую и третью позиции можно выбрать две…$$4 \cdot 3 \cdot 5 \cdot 4 = 240$$

Буквы в алфавитном порядке имеют номера от 0 до 6: А — 0, Г — 1, М — 2, Н — 3, С — 4, Т — 5, У — 6.

Последнее слово не может начинаться с У, поэтому максимальная первая буква — Т. Чтобы слово было максимально возможным и содержало ровно две буквы М, буквы М ставим в последние две позиции, а остальные позиции заполняем максимальной…

Упорядочим буквы по алфавиту: А, Г, Д, Е, П, Р. Для каждой фиксированной первой буквы можно составить $6^2$ слов, так как две оставшиеся позиции заполняются любыми из 6 букв.$$6^2 = 36$$

До слов, начинающихся с Е, идут все слова на А, Г и Д. Таких слов $3 \cdot 36 = 108$.$$3 \cdot 6^2 = 108$$

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

Каждую из оставшихся 5 позиций можно заполнить буквой В или буквой О.$$2^5$$

Буква К должна встретиться ровно один раз, поэтому выбираем одну из трёх позиций для неё.$$3$$

На каждую из двух оставшихся позиций можно поставить любую из четырёх букв: Ш, О, Л или А. Повторения разрешены.$$4 \cdot 4$$

Букву Б можно поставить на одну из четырёх позиций.$$4$$

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

В восьмеричной системе счисления используются цифры 0, 1, 2, 3, 4, 5, 6, 7. Первая цифра пятизначного числа не может быть равна 0.

Разбиваем записи на группы в зависимости от положения единственной цифры 6. При подсчёте учитываем, что соседние с 6 цифры должны быть чётными, а остальные цифры не должны быть равны 6.

Считаем левую верхнюю клетку начальной: её монета входит в сумму каждого маршрута.

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

В алфавитном порядке буквы расположены так: Е, И, К, Н, У, Ч.

Перед буквой Ч находятся 5 букв. Для каждой из них два следующих символа можно выбрать 6 способами каждый.$$5 \cdot 6^2 = 180$$

В алфавитном порядке заданные буквы располагаются так: А, Е, К, Н, Т, Ц. Слова, начинающиеся с Н, Т или Ц, не подходят. Последние подходящие слова начинаются с К.

Нумерация слов соответствует шестиричной системе счисления с цифрами 0, 1, 2, 3, 4, 5, которым соответствуют буквы А, Е, К, Н, Т, Ц.

В алфавитном порядке данные буквы расположены так: А, Г, Д, Е, П, Р. До буквы Р стоят 5 букв.

Для каждого выбора первой буквы существует 6 вариантов второй и 6 вариантов третьей буквы.$$6 \cdot 6 = 36$$

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

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

Буквы в алфавитном порядке имеют номера: Е — 1, И — 2, О — 3, Р — 4, Т — 5, Я — 6.

Чтобы слово было последним и не начиналось с Е, И или О, оно должно начинаться с Я. Ровно одна буква Я уже использована, поэтому остальные позиции должны быть не больше Т.

Обозначим через $max[i][j]$ и $min[i][j]$ максимальную и минимальную суммы, которые можно получить при попадании в клетку $(i,j)$.

Для каждой клетки рассматриваем только те переходы сверху или слева, которые не пересекают стену.$$max[i][j] = a[i][j] + \max(max[i-1][j], max[i][j-1])$$

Единственную букву Р можно поставить на любую из четырёх позиций.$$4$$

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

В алфавитном порядке буква С идёт после букв Е, Н и О.

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