Задание 8 ЕГЭ по информатике

1. 1.

   from itertools import product
   alph = 'АБВ'
   count = 0
   for w in product(alph, repeat=3):
       word = ''.join(w)
       if word.count('А') == 1:
           count += 1
   print(count)   # 12

Ответ: Прямой перебор всех 27 слов даёт 12

1. 1. Шаг 1. Разделим задачу на два независимых выбора: где стоят буквы Л и что стоит на остальных местах.
2. 2. Шаг 2. Выбор позиций. Из шести мест надо выбрать два под букву Л. Порядок здесь не важен — обе буквы одинаковы, — значит это сочетания: C(6,2) = 6 · 5 / 2 = 15 способов.
3. 3. Шаг 3. Заполнение остальных четырёх мест. На каждое годится любая буква, кроме Л (иначе букв Л станет больше двух), то есть четыре варианта: А, Д, К, О. По правилу произведения это 4⁴ = 256.
4. 4. Шаг 4. Два выбора независимы, значит перемножаем: 15 · 256 = 3840.
5. 5.

   Шаг 5. Проверка перебором. Программа на четыре строки считает то же самое и заодно страхует от ошибки в рассуждении:

   from itertools import product

   alph = 'АДКЛО'
   count = 0
   for w in product(alph, repeat=6):
       if w.count('Л') == 2:
           count += 1
   print(count)

6. 6. Шаг 6. Перебор проходит 5⁶ = 15 625 слов — мгновенно. Обратите внимание: w здесь кортеж букв, и w.count('Л') считает буквы прямо в нём, склеивать его в строку не обязательно.
7. 7. Типичная ошибка этой задачи — взять 4⁴ · 6 вместо 4⁴ · C(6,2), то есть посчитать, что букву Л ставят «в одно из шести мест» дважды. Так получаются упорядоченные пары позиций, и каждое слово учитывается дважды: ответ выходит вдвое больше. Перебор такую ошибку ловит сразу.

Ответ: 3840

1. 1.

   from itertools import product

   count = 0
   for w in product('0123', repeat=5):
       if w[0] == '0':
           continue                      # не пятизначное
       if w.count('3') != 1:
           continue                      # ровно одна тройка
       if all({w[i], w[i + 1]} != {'0', '3'} for i in range(4)):
           count += 1
   print(count)

2. 2. Шаг 1. Алфавит четверичной системы — цифры 0, 1, 2, 3. Всего кортежей длины 5 получается 4⁵ = 1024, и перебрать их можно хоть тысячу раз подряд.
3. 3. Шаг 2. Первый continue отсеивает числа, начинающиеся с нуля: слово «01230» не является пятизначным числом. Остаётся 3 · 4⁴ = 768 кандидатов.
4. 4. Шаг 3. Второй continue оставляет те, где тройка ровно одна. Не «хотя бы одна» и не «не более одной» — условие читается буквально.
5. 5. Шаг 4. Проверка соседства. Пара соседних цифр {w[i], w[i+1]} превращена в множество, и сравнение с {'0','3'} истинно, если рядом стоят ноль и тройка в любом порядке. Это короче, чем расписывать два случая: «0 слева, 3 справа» и наоборот. all(...) требует, чтобы условие выполнялось для всех четырёх соседних пар.
6. 6. Шаг 5. Проверим на примере. Число 13203: тройка встречается дважды — отсеивается вторым continue. Число 10320: тройка одна, но пара (3, 2) в порядке, а вот (0, 3) на местах 2–3 запрещена → отсеивается. Число 13120: тройка одна; пары (1,3), (3,1), (1,2), (2,0) — ни одна не равна {0,3} → подходит.
7. 7. Шаг 6. Программа печатает 174. Заметьте, насколько дешевле это, чем разбирать случаи руками: «тройка на первом месте», «тройка на втором месте, слева не ноль», и так далее — пять случаев с подслучаями.

Ответ: 174

1. 1.

   from itertools import product

   alph = sorted('МАСЛО')          # ['А', 'Л', 'М', 'О', 'С']
   nomer = 0
   for w in product(alph, repeat=5):
       nomer += 1
       word = ''.join(w)
       if word.count('А') <= 1 and word.count('М') == 2 and 'Л' not in word:
           print(nomer, word)
           break

2. 2. Шаг 1. sorted('МАСЛО') даёт список букв в алфавитном порядке: А, Л, М, О, С. Это ключевой момент: сортировать обязательно, иначе product пойдёт в порядке исходной строки, и нумерация будет чужой.
3. 3. Шаг 2. product по отсортированному алфавиту выдаёт слова ровно в алфавитном порядке: ААААА, ААААЛ, ААААМ, ААААО, ААААС, АААЛА, … Поэтому достаточно вести счётчик и остановиться на первом подходящем.
4. 4. Шаг 3. Счётчик увеличивается до проверки условия, потому что нумерация начинается с 1: первое же слово ААААА должно получить номер 1, а не 0.
5. 5. Шаг 4. Программа печатает 319 АММОО. Проверим условия глазами: букв А одна (не более одной ✔), букв М две ✔, буквы Л нет ✔
6. 6. Шаг 5. Проверка счётом, без перебора. Переводим АММОО в цифры по нашей нумерации: А = 0, М = 2, М = 2, О = 3, О = 3. Получилось пятеричное число 02233.
7. 7. Шаг 6. Считаем его значение: 0 · 5⁴ + 2 · 5³ + 2 · 5² + 3 · 5 + 3 = 0 + 2 · 125 + 2 · 25 + 15 + 3 = 250 + 50 + 15 + 3 = 318.
8. 8. Шаг 7. Номер равен значению плюс один: 318 + 1 = 319. Совпало с перебором.
9. 9. Шаг 8. Зачем нужны оба способа. Перебор надёжнее и пишется быстрее, но работает, только пока слов немного. Если бы в задании стояла длина 12 при алфавите из шести букв, слов было бы два миллиарда, и перебор не прошёл бы — тогда остаётся только счёт.

Ответ: 319

1. 1. Шаг 1. Алфавит по порядку: К, О, Т, то есть К = 0, О = 1, Т = 2. Основание системы равно 3, длина слова 5. Всего слов 3⁵ = 243, значит сотое существует.
2. 2. Шаг 2. Вычитаем единицу: номер 100 соответствует значению 99. Единицу вычитают потому, что нумерация слов начинается с 1, а значения чисел — с 0.
3. 3. Шаг 3. Переводим 99 в троичную систему делением с остатком. 99 : 3 = 33, остаток 0. 33 : 3 = 11, остаток 0. 11 : 3 = 3, остаток 2. 3 : 3 = 1, остаток 0. 1 : 3 = 0, остаток 1.
4. 4. Шаг 4. Остатки выписываем снизу вверх, то есть в обратном порядке получения: 1, 0, 2, 0, 0. Получилось число 10200₃. Проверим: 1 · 81 + 0 · 27 + 2 · 9 + 0 · 3 + 0 = 81 + 18 = 99 ✔
5. 5. Шаг 5. Разрядов вышло ровно пять — дополнять нулями слева не понадобилось. Если бы номер был маленьким, скажем 4 (значение 3, то есть 10₃), пришлось бы дописать нули до длины 5: 00010.
6. 6. Шаг 6. Заменяем цифры буквами: 1 → О, 0 → К, 2 → Т, 0 → К, 0 → К. Слово: ОКТКК.
7. 7.

   Шаг 7. Проверка перебором:

   from itertools import product

   alph = sorted('КОТ')
   nomer = 0
   for w in product(alph, repeat=5):
       nomer += 1
       if nomer == 100:
           print(''.join(w))
           break

   Программа печатает ОКТКК — совпало.

Ответ: ОКТКК