О задании
В статьях ранее мы вспомнили комбинаторные подходы расположения элементов и научились работать с функциями product() и permutations() их модуля itertools в Python. Теперь настало время применить все наши знания на практике и научиться решать 8 задания ЕГЭ по информатике.
Эти задания нацелены на проверку умений проверять комбинаторные подходы для решения практических задач. В 8 заданиях обычно требуется найти количество возможных вариантов расположения исходных символов и определить порядковый номер подходящей под условие комбинации.
Можно, конечно, решать данные задания и ручными методами. Но в прошлой статье мы как раз разобрали две функции модуля itertools, которые и позволяют быстро генерировать различные комбинации и перестановки элементов, что нередко требуется при решении комбинаторных задач.
Использование готовых инструментов не только экономит время, но и снижает риск ошибок, связанных с ручными расчётами. Более того, многие реальные задачи ЕГЭ можно решить буквально несколькими строками кода, если правильно применить эти функции.
Что же касается самих заданий 8, то их можно разделить на три типа:
- В заданиях первого типа нам дан алфавит и от нас требуется найти порядковый номер слова, составленного из букв данного алфавита, которое будет удовлетворять заданному условию
- В заданиях второго типа нужно найти количество комбинаций цифр, в которых будет выполняться требуемое условие
- А задания третьего типа похожи на задания первого, основное отличие заключается в том, что в составляемых из букв данного алфавита словах, буквы не должны повторяться
Как обычно, на каждый тип выделим отдельную статью. А в этой статье рассмотрим алгоритм решения 8 заданий первого типа. Давайте приступать.
Алгоритм решения
Начнём с типовой формулировки 8 задания:
«Все шестибуквенные слова, в составе которых могут быть только русские буквы П, О, Л, Ь, З, А, записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.
1. АААААА
2. АААААЗ
3. АААААЛ
4. АААААО
5. АААААП
6. АААААЬ
7. ААААЗА
…
Под каким номером в списке идёт первое слово, которое содержит не более одной буквы Ь, ровно одну букву А и не более двух букв З?»
Итак, у нас есть 6 букв: П, О, Л, Ь, З, А. Из них составляются комбинации длиной 6 символов, причем все эти комбинации отсортированы в алфавитном порядке. Таким образом, производится операция размещения с повторением. Давайте вспомним, какая функция модуля itertools позволяет осуществить размещения с повторением.
Конечно же, это функция product()! Пока остановимся на этом моменте и получим все размещения с повторением исходных букв с помощью данной функции.
Первым делом выпишем все наши буквы в виде одной строки:
Теперь выведем на экран все размещения с повторением, полученные с помощью product(). Поскольку нам нужны только шестибуквенные слова, то передаём в качестве аргумента repeat число 6:
Что мы здесь видим? Размещения начинаются с первого символа — П — и далее последний, шестой, элемент размещения заменяется на последующие буквы: О, Л, Ь и так далее.
Как нам получить шестибуквенные слова в алфавитном порядке? Давайте просто отсортируем исходную строку с помощью функции sorted().
Готово, мы получили ровно такой же список, какой представлен в условии задания! Идём дальше. Нужно определить порядковый номер слова. Вспомним, что с подобной задачей мы уже сталкивались ранее, в 9 заданиях. Здесь как нельзя кстати придётся функция enumerate()! Сейчас уже не будем подробно разбирать её, ведь мы уже работали с ней ранее, в статье про второй тип 9 заданий.
Добавим цикл, который будет перебирать комбинации индекса и слова, полученных из результата работы функции product():
Далее нам понадобится проверять наличие определённых букв в полученных словах. После работы функции product() в переменной letters у нас будет список из букв. Нужно как-то из этого списка получить строку. Для этого будем на каждой итерации цикла собирать из списка букв целое слово с помощью метода join:
В итоге первые 6 значений переменной word будут такими:
АААААА
АААААЗ
АААААЛ
АААААО
АААААП
АААААЬ
Отлично, мы на финишной прямой. Осталось лишь переписать все условия из формулировки задания и получить нужный номер. Требуется, чтобы первое подходящее слово содержало:
- Не более одной буквы Ь
- Ровно одну букву А
- Не более двух букв З
На язык Python это условие можно перевести так:
Добавляем эту условную конструкцию в нашу программу и, как только она выполнится, выводим значение индекса и завершаем цикл:
Все, наша программа готова. Запускаем её и видим результат: 1599. Именно это число и будет ответом на наше задание.
Пример 1
Рассмотрим еще одно задание:
«Все пятибуквенные слова, в составе которых могут быть только буквы Ф, О, К, У, С, записаны в алфавитном порядке и пронумерованы.
Вот начало списка:
1. ККККК
2. ККККО
3. ККККС
4. ККККУ
5. ККККФ
…
Под каким номером в списке идёт последнее слово, которое не содержит букв Ф и содержит ровно две буквы У?»
Сразу отметим главное отличие от прошлого задания: теперь нам нужно найти не первое, а последнее слово, удовлетворяющее условию. Значит, придётся дождаться окончания работы всего цикла и каждый раз записывать номер подходящей под условие строки. Следовательно, последний записанный номер и будет нужным нам номером последнего слова.
Это можно сделать разными способами: сохранять все номера в список или же перезаписывать значение одной-единственной переменной, указывающей на последний подходящий номер строки. Именно вторым способом мы и воспользуемся.
Начало у нас будет таким же, как и в прошлом задании, только в этот раз сразу запишем слово и отсортируем его в одной строчке:
Теперь создадим переменную, в которой будем хранить нужный нам последний номер. Изначально приравняем её значение к 0:
Далее идёт уже использованный ранее цикл. Обратите внимание, что теперь работаем с пятибуквенными словами, значит в repeat передаём число 5:
Осталось лишь переписать условие. Нам нужно, чтобы в слове не было букв «Ф» и количество букв «У» равнялось двум. Запишем это так:
При каждом выполнении этого условия будем сохранять текущее значение индекса (idx) в переменную ans. После завершения работы цикла выведем значение ans, это и будет ответом. Полный код для решения данного задания выглядит так:
Запускаем его и видим на экране число 2313, которое и пишем в ответ.
Пример 2
Для закрепления рассмотрим еще одно задание со схожей формулировкой:
«Все пятибуквенные слова, составленные из букв С, Т, Р, О, К, А, записаны в алфавитном порядке и пронумерованы.
Ниже приведено начало списка.
1. AAAAA
2. ААААК
3. ААААО
4. AAAAP
5. AAAAC
6. AAAAT
…
Определите, под каким номером в этом списке стоит последнее слово с нечетным номером, которые не начинается с букв А или Л и при этом содержит в своей записи ровно одну букву С.»
Особо останавливаться на решение уже не будем, начало, вплоть до условия цикла, будет аналогичным предыдущему:
Разберём условие по пунктам:
- Номер слова нечётный: idx % 2. Такая запись для нечётных значений idx вернёт 1, которые в Python расценивается как Истина
- Слово не начинается с А или Л: word[0] not in ‘АЛ’. То есть первая буква слова не должна быть среди букв «АЛ»
- Слово содержит ровно одну букву С: count(‘С’) == 1. Здесь ничего необычного — количество букв «С» должно равняться 1.
Записываем это условие и при его выполнении обновляем значение ans, которое выводим на экран после завершения работы цикла:
Запускаем нашу программу и получаем ответ на это задание — число 7775.
Итоги
Мы с вами освоили решение первого типа 8 заданий ЕГЭ по информатике. Как вы видите, все решения шаблонные, главное — верно переписать условие, которому должны соответствовать нужные слова.
Давайте выведем такой шаблон для заданий, в которых требуется найти первое подходящее слово:
Здесь:
- *1 — слово из условия
- *2 — количество букв в составляемых словах
- *3 — условие, которому должны соответствовать подходящие слова
По аналогии выведем такой шаблон для заданий, в которых требуется найти последнее подходящее слово:
Условные обозначения здесь аналогичные.
В следующей статье мы возьмёмся за решения второго типа 8 заданий и научимся искать все возможные комбинации символов, удовлетворяющие условию задания.