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

Слова в алфавитном порядке и подсчёт комбинаций

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

Главная идея

  • Слова в алфавитном порядке из k букв — это числа в k-ичной системе по возрастанию.
  • Номер слова = его значение как числа + 1.
  • Всего слов длины n из k букв: kn.

Как решать на Python

  • product(letters, repeat=n) выдаёт слова в порядке букв в строке — поэтому сначала sorted.
  • enumerate(..., start=1) даёт номер слова.
  • w.count('О'), w[0], len(set(w)) — основные проверки.

Типичные ошибки

  • Забыть отсортировать буквы.
  • Нумеровать с нуля.
  • Для чисел — разрешить ведущий ноль.

Разобранные варианты

Сначала реши сам, потом открой разбор. В каждом разборе есть программа на Python.

Вариант 1

последнее слово с условиями

Все 6-буквенные слова, составленные из букв Г, Р, О, З, А, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. АААААА
2. АААААГ
3. АААААЗ
4. АААААО
5. АААААР
……
Определите, под каким номером в этом списке стоит последнее слово с нечётным номером, которое заканчивается гласной буквой и при этом содержит в своей записи ровно две буквы А.

Разбор

Шаг 1. Список — это числа. Букв 5, упорядочим их: А, Г, З, О, Р. Заменим буквы цифрами 0…4: тогда слова идут как 6-значные числа в 5-ичной системе по возрастанию, а номер слова = значение числа + 1.

Шаг 2. Перебор. Вручную искать последнее подходящее слово долго и легко ошибиться, поэтому переберём все слова программой в алфавитном порядке и проверим условия.

Шаг 3. Проверка ответа. Найденное слово — РРРРАА. По цифрам: 4444005 = 15600, номер 15600 + 1 = 15601.

Ответ: 15601

Решение на Python.

from itertools import product

letters = sorted('АГЗОР')        # алфавитный порядок
ans = None
for i, p in enumerate(product(letters, repeat=6), start=1):
    w = ''.join(p)
    if (w[-1] in 'АО') and (w.count('А') == 2) and i % 2 == 1:
        ans = i
print(ans)

Вариант 2

номер слова

Все 4-буквенные слова, составленные из букв Г, Р, О, З, А, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. АААА
2. АААГ
3. АААЗ
4. АААО
5. АААР
……
Под каким номером в этом списке стоит слово ГАРГ?

Разбор

Шаг 1. Упорядочим буквы: А → 0, Г → 1, З → 2, О → 3, Р → 4. Список слов — это 4-значные числа в 5-ичной системе по возрастанию, начиная с нуля.

Шаг 2. Слово ГАРГ → 10415 = 1·53 + 0·52 + 4·51 + 1·50 = 146.

Шаг 3. Нумерация начинается с 1, поэтому номер слова 146 + 1 = 147.

Ответ: 147

Решение на Python.

from itertools import product

letters = sorted('АГЗОР')
for i, p in enumerate(product(letters, repeat=4), start=1):
    if ''.join(p) == 'ГАРГ':
        print(i)
        break

Вариант 3

количество слов

Петя составляет 4-буквенные слова из букв К, Р, У, Ж, Е, В, А. Каждую букву можно использовать любое количество раз или не использовать совсем. Сколько различных слов может составить Петя, если каждое слово содержит ровно одну букву К и начинается с согласной буквы?

Разбор

Всего слов без условий: 74 = 2401. Два условия сразу удобнее проверить перебором: перебираем все слова и считаем подходящие.

Как рассуждать без компьютера. Разбиваем на случаи по позициям «особых» букв и перемножаем число вариантов для каждой позиции (правило произведения), случаи складываем (правило суммы).

Для самопроверки — сколько подходящих слов начинается с каждой буквы: А — 0, В — 108, Е — 0, Ж — 108, К — 216, Р — 108, У — 0; всего 540.

Ответ: 540

Решение на Python.

from itertools import product

count = 0
for p in product('АВЕЖКРУ', repeat=4):
    w = ''.join(p)
    if (w.count('К') == 1) and (w[0] in 'ВЖКР'):
        count += 1
print(count)

Вариант 4

первое слово с условиями

Все 5-буквенные слова, составленные из букв К, Р, У, Ж, Е, В, А, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААВ
3. ААААЕ
4. ААААЖ
5. ААААК
……
Определите, под каким номером в этом списке стоит первое слово с нечётным номером, которое состоит из различных букв и при этом заканчивается гласной буквой.

Разбор

Шаг 1. Список — это числа. Букв 7, упорядочим их: А, В, Е, Ж, К, Р, У. Заменим буквы цифрами 0…6: тогда слова идут как 5-значные числа в 7-ичной системе по возрастанию, а номер слова = значение числа + 1.

Шаг 2. Перебор. Вручную искать первое подходящее слово долго и легко ошибиться, поэтому переберём все слова программой в алфавитном порядке и проверим условия.

Шаг 3. Проверка ответа. Найденное слово — АВЕЖУ. По цифрам: 012367 = 468, номер 468 + 1 = 469.

Ответ: 469

Решение на Python.

from itertools import product

letters = sorted('АВЕЖКРУ')        # алфавитный порядок
ans = None
for i, p in enumerate(product(letters, repeat=5), start=1):
    w = ''.join(p)
    if (len(set(w)) == len(w)) and (w[-1] in 'АЕУ') and i % 2 == 1:
        ans = i
        break
print(ans)

Вариант 5

7-ичные числа

Сколько существует семеричных 5-значных чисел, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?

Разбор

Что важно. В 7-ичной системе цифры от 0 до 6, первая цифра 5-значного числа не может быть нулём.

Решение перебором. Перебираем все числа от 74 до 75 − 1, переводим в 7-ичную систему и проверяем условие. Другой способ — перебрать наборы цифр через product, отбросив те, что начинаются с 0.

Ответ: 180

Решение на Python.

def to_base(x, k):
    s = ''
    while x > 0:
        s = str(x % k) + s
        x //= k
    return s

count = 0
for x in range(7 ** 4, 7 ** 5):
    s = to_base(x, 7)
    if len(set(s)) == len(s) and all(int(s[i]) % 2 != int(s[i + 1]) % 2 for i in range(len(s) - 1)):
        count += 1
print(count)

Вариант 6

последнее слово с условиями

Все 4-буквенные слова, составленные из букв П, А, Р, У, С, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. АААА
2. АААП
3. АААР
4. АААС
5. АААУ
……
Определите, под каким номером в этом списке стоит последнее слово с чётным номером, которое содержит ровно одну букву П и при этом содержит не менее двух букв У.

Разбор

Шаг 1. Список — это числа. Букв 5, упорядочим их: А, П, Р, С, У. Заменим буквы цифрами 0…4: тогда слова идут как 4-значные числа в 5-ичной системе по возрастанию, а номер слова = значение числа + 1.

Шаг 2. Перебор. Вручную искать последнее подходящее слово долго и легко ошибиться, поэтому переберём все слова программой в алфавитном порядке и проверим условия.

Шаг 3. Проверка ответа. Найденное слово — УУУП. По цифрам: 44415 = 621, номер 621 + 1 = 622.

Ответ: 622

Решение на Python.

from itertools import product

letters = sorted('АПРСУ')        # алфавитный порядок
ans = None
for i, p in enumerate(product(letters, repeat=4), start=1):
    w = ''.join(p)
    if (w.count('П') == 1) and (w.count('У') >= 2) and i % 2 == 0:
        ans = i
print(ans)

Вариант 7

количество слов

Петя составляет 6-буквенные слова из букв Г, Р, О, З, А. Каждую букву можно использовать любое количество раз или не использовать совсем. Сколько различных слов может составить Петя, если каждое слово содержит в своей записи ровно две буквы О и начинается с согласной буквы?

Разбор

Всего слов без условий: 56 = 15625. Два условия сразу удобнее проверить перебором: перебираем все слова и считаем подходящие.

Как рассуждать без компьютера. Разбиваем на случаи по позициям «особых» букв и перемножаем число вариантов для каждой позиции (правило произведения), случаи складываем (правило суммы).

Для самопроверки — сколько подходящих слов начинается с каждой буквы: А — 0, Г — 640, З — 640, О — 0, Р — 640; всего 1920.

Ответ: 1920

Решение на Python.

from itertools import product

count = 0
for p in product('АГЗОР', repeat=6):
    w = ''.join(p)
    if (w.count('О') == 2) and (w[0] in 'ГЗР'):
        count += 1
print(count)

Вариант 8

номер слова

Все 5-буквенные слова, составленные из букв Д, Е, К, А, Б, Р, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААБ
3. ААААД
4. ААААЕ
5. ААААК
……
Под каким номером в этом списке стоит слово ЕАДРБ?

Разбор

Шаг 1. Упорядочим буквы: А → 0, Б → 1, Д → 2, Е → 3, К → 4, Р → 5. Список слов — это 5-значные числа в 6-ичной системе по возрастанию, начиная с нуля.

Шаг 2. Слово ЕАДРБ → 302516 = 3·64 + 0·63 + 2·62 + 5·61 + 1·60 = 3991.

Шаг 3. Нумерация начинается с 1, поэтому номер слова 3991 + 1 = 3992.

Ответ: 3992

Решение на Python.

from itertools import product

letters = sorted('АБДЕКР')
for i, p in enumerate(product(letters, repeat=5), start=1):
    if ''.join(p) == 'ЕАДРБ':
        print(i)
        break

Вариант 9

7-ичные числа

Сколько существует семеричных 4-значных чисел, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?

Разбор

Что важно. В 7-ичной системе цифры от 0 до 6, первая цифра 4-значного числа не может быть нулём.

Решение перебором. Перебираем все числа от 73 до 74 − 1, переводим в 7-ичную систему и проверяем условие. Другой способ — перебрать наборы цифр через product, отбросив те, что начинаются с 0.

Ответ: 126

Решение на Python.

def to_base(x, k):
    s = ''
    while x > 0:
        s = str(x % k) + s
        x //= k
    return s

count = 0
for x in range(7 ** 3, 7 ** 4):
    s = to_base(x, 7)
    if len(set(s)) == len(s) and all(int(s[i]) % 2 != int(s[i + 1]) % 2 for i in range(len(s) - 1)):
        count += 1
print(count)

Вариант 10

последнее слово с условиями

Все 4-буквенные слова, составленные из букв Ф, И, Н, А, Л, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. АААА
2. АААИ
3. АААЛ
4. АААН
5. АААФ
……
Определите, под каким номером в этом списке стоит последнее слово, которое состоит из различных букв и при этом содержит ровно одну букву А.

Разбор

Шаг 1. Список — это числа. Букв 5, упорядочим их: А, И, Л, Н, Ф. Заменим буквы цифрами 0…4: тогда слова идут как 4-значные числа в 5-ичной системе по возрастанию, а номер слова = значение числа + 1.

Шаг 2. Перебор. Вручную искать последнее подходящее слово долго и легко ошибиться, поэтому переберём все слова программой в алфавитном порядке и проверим условия.

Шаг 3. Проверка ответа. Найденное слово — ФНЛА. По цифрам: 43205 = 585, номер 585 + 1 = 586.

Ответ: 586

Решение на Python.

from itertools import product

letters = sorted('АИЛНФ')        # алфавитный порядок
ans = None
for i, p in enumerate(product(letters, repeat=4), start=1):
    w = ''.join(p)
    if (len(set(w)) == len(w)) and (w.count('А') == 1):
        ans = i
print(ans)

Для самостоятельного решения

Варианты 11–15 без разборов. Ответ можно проверить кнопкой.

Вариант 11

первое слово с условиями

Все 5-буквенные слова, составленные из букв П, А, Р, У, С, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААП
3. ААААР
4. ААААС
5. ААААУ
……
Определите, под каким номером в этом списке стоит первое слово с чётным номером, которое содержит в своей записи ровно две буквы У и при этом начинается с согласной буквы.

Вариант 12

количество слов

Петя составляет 5-буквенные слова из букв М, О, Р, Е. Каждую букву можно использовать любое количество раз или не использовать совсем. Сколько различных слов может составить Петя, если каждое слово начинается с согласной буквы и содержит не менее двух букв О?

Вариант 13

8-ичные числа

Сколько существует восьмеричных 5-значных чисел, которые не содержат в своей записи цифру 1 и в которых все цифры различны?

Вариант 14

номер слова

Все 6-буквенные слова, составленные из букв П, А, Р, У, С, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. АААААА
2. АААААП
3. АААААР
4. АААААС
5. АААААУ
……
Под каким номером в этом списке стоит слово ПРУССП?

Вариант 15

первое слово с условиями

Все 5-буквенные слова, составленные из букв М, О, Р, Е, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ЕЕЕЕЕ
2. ЕЕЕЕМ
3. ЕЕЕЕО
4. ЕЕЕЕР
5. ЕЕЕМЕ
……
Определите, под каким номером в этом списке стоит первое слово с нечётным номером, которое содержит не менее двух букв Е и при этом начинается с согласной буквы.