Алгоритм решения задания 8. Часть 1

О задании

В предыдущих статьях мы вспомнили основные комбинаторные понятия и научились работать с функциями product() и permutations() из модуля itertools. Теперь применим эти знания к заданию 8 ЕГЭ по информатике.

Задание 8 проверяет умение применять комбинаторные подходы. Обычно нужно найти количество подходящих последовательностей или порядковый номер слова, удовлетворяющего условию.

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

Готовые инструменты экономят время и снижают риск ошибок в расчётах. Многие варианты задания 8 решаются несколькими строками кода, если правильно выбрать функцию.

Условно разделим задания на три типа:

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

Каждому типу посвятим отдельную статью. Здесь разберём первый тип и научимся находить номер подходящего слова.

Алгоритм решения

Начнём с типовой формулировки задания 8:

Все шестибуквенные слова, в составе которых могут быть только русские буквы П, О, Л, Ь, З, А, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.

1. АААААА
2. АААААЗ
3. АААААЛ
4. АААААО
5. АААААП
6. АААААЬ
7. ААААЗА
…

Под каким номером в списке идёт первое слово, которое содержит не более одной буквы Ь, ровно одну букву А и не более двух букв З?

Открыть задание

У нас есть шесть букв: П, О, Л, Ь, З и А. Из них составляются слова длины 6, причём буквы могут повторяться. Значит, нужно сгенерировать размещения с повторениями.

Для этого подходит функция product(). Сначала получим все шестибуквенные последовательности из данных букв.

Запишем буквы из условия одной строкой:

alph = "ПОЛЬЗА"

Передадим строку в product() и укажем repeat=6, потому что слова должны состоять из шести букв:

from itertools import product

alph = "ПОЛЬЗА"
result = product(alph, repeat=6)

for res in result:
    print(res)

>>>('П', 'П', 'П', 'П', 'П', 'П')
>>>('П', 'П', 'П', 'П', 'П', 'О')
>>>('П', 'П', 'П', 'П', 'П', 'Л')
>>>('П', 'П', 'П', 'П', 'П', 'Ь')
>>>('П', 'П', 'П', 'П', 'П', 'З')
>>>('П', 'П', 'П', 'П', 'П', 'А')
…

Последовательности начинаются с буквы П, потому что product() сохраняет порядок символов исходной строки. Последняя позиция перебирается быстрее остальных: П, О, Л, Ь и так далее.

Чтобы получить слова в алфавитном порядке, отсортируем исходные буквы с помощью sorted().

from itertools import product

alph = "ПОЛЬЗА"
alph = sorted(alph)
result = product(alph, repeat=6)

for res in result:
    print(res)

>>>('А', 'А', 'А', 'А', 'А', 'А')
>>>('А', 'А', 'А', 'А', 'А', 'З')
>>>('А', 'А', 'А', 'А', 'А', 'Л')
>>>('А', 'А', 'А', 'А', 'А', 'О')
>>>('А', 'А', 'А', 'А', 'А', 'П')
>>>('А', 'А', 'А', 'А', 'А', 'Ь')

Готово: список совпадает с началом списка из условия. Теперь нужно определить номер слова. Для нумерации воспользуемся enumerate(), передав start=1, потому что список нумеруется с единицы.

Добавим цикл, который перебирает номер и набор букв из результата product():

from itertools import product

alph = "ПОЛЬЗА"
alph = sorted(alph)

for idx, letters in enumerate(product(alph, repeat=6), start=1):

Функция product() возвращает кортежи букв. Чтобы проверять условия как для обычной строки, на каждой итерации соединим буквы методом join():

from itertools import product

alph = "ПОЛЬЗА"
alph = sorted(alph)

for idx, letters in enumerate(product(alph, repeat=6), start=1):
    word = "".join(letters)

Первые шесть значений переменной word будут такими:

АААААА
АААААЗ
АААААЛ
АААААО
АААААП
АААААЬ

Мы почти закончили. Осталось записать условия для первого подходящего слова:

Не более одной буквы Ь;
Ровно одна буква А;
Не более двух букв З.

На Python это условие записывается так:

if word.count("Ь") <= 1 and word.count("А") == 1 and word.count("З") <= 2:

Добавим условие в программу. Как только найдётся первое подходящее слово, выведем его номер и завершим цикл командой break:

from itertools import product

alph = "ПОЛЬЗА"
alph = sorted(alph)

for idx, letters in enumerate(product(alph, repeat=6), start=1):
    word = "".join(letters)
    if (word.count("Ь") <= 1
        and word.count("А") == 1
        and word.count("З") <= 2):
        print(idx)
        break

Всё, программа готова. После запуска получаем 1599 — это ответ.

Пример 1

Рассмотрим ещё одно задание:

Все 5-буквенные слова, в составе которых могут быть только буквы Ф, О, К, У, С, записаны в алфавитном порядке и пронумерованы. Ниже приведено начало списка.

1. ККККК
2. ККККО
3. ККККС
4. ККККУ
5. ККККФ
…

Под каким номером в списке идёт последнее слово, которое не содержит букв Ф и содержит ровно две буквы У?

Открыть задание

Главное отличие: теперь нужно найти последнее подходящее слово. Поэтому цикл должен завершиться полностью, а номер каждого подходящего слова будет заменять предыдущий сохранённый номер.

Можно сохранить все подходящие номера в список, но достаточно одной переменной. После завершения цикла в ней останется номер последнего подходящего слова.

Начало решения такое же. На этот раз сразу передадим строку в sorted():

from itertools import product

alph = sorted('ФОКУС')

Создадим переменную для последнего подходящего номера и зададим ей начальное значение 0:

from itertools import product

alph = sorted(‘ФОКУС’)

ans = 0

Далее используем знакомый цикл. Слова пятибуквенные, поэтому указываем repeat=5:

from itertools import product

alph = sorted('ФОКУС')

ans = 0

for idx, letters in enumerate(product(alph, repeat=5), start=1):
    word = ''.join(letters)

Перепишем условие: в слове не должно быть буквы Ф, а буква У должна встречаться ровно два раза.

if 'Ф' not in word and word.count('У') == 2

При каждом выполнении условия сохраняем idx в ans. После завершения цикла выводим ans:

from itertools import product

alph = sorted('ФОКУС')

ans = 0

for idx, letters in enumerate(product(alph, repeat=5), start=1):
    word = ''.join(letters)
    if 'Ф' not in word and word.count('У') == 2:
        ans = idx

print(ans)

После запуска получаем 2313. Это число и записываем в ответ.

Пример 2

Для закрепления рассмотрим ещё одно задание со схожей формулировкой:

Все пятибуквенные слова, составленные из букв С, Т, Р, О, К, А, записаны в алфавитном порядке и пронумерованы. Ниже приведено начало списка.

1. AAAAA
2. ААААК
3. ААААО
4. AAAAP
5. AAAAC
6. AAAAT
…

Определите, под каким номером этом списке стоит последнее слово с нечетным номером, которые не начинается с букв А или Л и при этом содержит в своей записи ровно одну букву С.

Открыть задание

Подробно останавливаться на решении уже не будем: начало программы до условия будет таким же, как в предыдущем примере.

from itertools import product

alph = sorted('СТРОКА')

ans = 0

for idx, letters in enumerate(product(alph, repeat=5), start=1):
    word = ''.join(letters)

Разберём условие по пунктам:

Номер слова нечётный: idx % 2 == 1;
Слово не начинается с А или Л: word[0] not in 'АЛ'. Буквы Л нет в алфавите, поэтому в этой формулировке фактически исключается только начальная А;
Слово содержит ровно одну букву С: count('С') == 1.

Запишем все условия. При каждом совпадении обновляем ans, а после завершения цикла выводим его значение:

from itertools import product

alph = sorted('СТРОКА')

ans = 0

for idx, letters in enumerate(product(alph, repeat=5), start=1):
    word = ''.join(letters)
    if idx % 2 == 1 and word[0] not in 'АЛ' and word.count('С') == 1:
        ans = idx

print(ans)

Программа выводит 7775. Это ответ.

Итоги

Мы освоили решение первого типа задания 8. Алгоритм повторяется от задачи к задаче: важно правильно составить алфавит, отсортировать его и без ошибок записать условия.

Сначала запишем шаблон для поиска первого подходящего слова:

from itertools import product

alph = sorted('*1')

for idx, letters in enumerate(product(alph, repeat=*2), start=1):
    word = "".join(letters)
    if *3:
        print(idx)
        break

Здесь:

*1 — алфавит из условия;
*2 — длина составляемых слов; это число нужно подставить без кавычек;
*3 — условие для подходящих слов.

Для поиска последнего подходящего слова используем такой шаблон:

from itertools import product

alph = sorted('*1')

ans = 0

for idx, letters in enumerate(product(alph, repeat=*2), start=1):
    word = ''.join(letters)
    if *3:
        ans = idx

print(ans)

Условные обозначения здесь те же.

В следующей статье перейдём ко второму типу задания 8 и научимся считать все последовательности, удовлетворяющие условию.

Алгоритм решения задания 8. Часть 1

О задании

Алгоритм решения

Пример 1

Пример 2

Итоги

Рекомендуемые статьи