Почему это важно?
В заданиях по информатике часто встречаются задачи на подсчёт слов по заданным условиям. Эти задачи кажутся громоздкими, но на самом деле решаются по понятному алгоритму — вручную или при помощи короткой программы.
🔹 Пример задания
Все 5-буквенные слова составлены из букв {С, Т, Р, О, К, А} и упорядочены в алфавитном порядке (А < К < О < Р < С < Т).
Найдите номер последнего слова с чётным номером, которое:
- не начинается с А, С или Т;
- содержит ровно две буквы «О».
1) Как устроен список слов
зададим «коды» букв по алфавиту (как цифры в 6-ричной системе):
А=0, К=1, О=2, Р=3, С=4, Т=5.
слово в списке ведёт себя как 5-значное 6-ричное число.
номер слова = значение + 1.
(значение — это b1⋅6^4+b2⋅6^3+b3⋅6^2+b4⋅6^1+b5, где bi — коды букв.)
2) Что значит «чётный номер»
чётный номер ⇔ (value+1) чётно ⇔ value нечётно.
в 6-ричной системе чётность value зависит только от последней «цифры» (все предыдущие умножаются на 6 и дают чётное).
значит номер чётный ⇔ индекс последней буквы нечётный ⇒ последняя ∈ {К(1), Р(3), Т(5)}.
3) Ищем последнее слово (лексикографически максимальное) под условия
- первая буква «не А,С,Т» ⇒ из {К, О, Р}. чтобы слово было последним, берём максимальную — Р.
- «ровно две О». так как первая уже Р, обе «О» должны стоять среди позиций 2–5.
- для чётного номера последняя выбирается максимально из {К, Р, Т} ⇒ Т.
- осталось расставить две «О» и ещё одну свободную букву между 2–4-й позициями так, чтобы слово было максимальным.
максимальная свободная буква — Т. чтобы получить наибольшее слово, ставим эту букву как можно раньше (на 2-ю позицию), а дальше — две «О».
получаем РТООТ.
почему это точно максимум?
- если сделать 2-ю букву меньше, чем Т (например, С), слово сразу станет меньше лексикографически; поздние позиции уже не спасут.
- если пытаться поставить «не-О» на 3-ю или 4-ю позицию, на 2-й придётся поставить «О», что хуже, чем «Т» на 2-й.
4) Считаем номер слова РТООТ вручную
коды: Р=3, Т=5, О=2, О=2, Т=5.
value=3·6^4+5·6^3+2·6^2+2·6+5=3·1296+5·216+2·36+12+5=3888+1080+72+12+5=5057.
номер = 5057 + 1 = 5058.
5) Код на Python для решения этой же задачи и самопроверки
Результат: (5058, 'РТООТ')
🔹 Ответ
- Слово: РТООТ
- Номер: 5058
🔹 Вывод
- Для сложных на первый взгляд задач удобно сначала формализовать условия.
- После — либо аккуратно подсчитывать вручную, либо проверить себя с помощью короткой программы.
- Такой подход позволяет безошибочно находить ответ, даже если вариантов очень много.
А если хотите получать больше свежей и полезной информации - переходите в мой телеграмм канал, где часто публикуются свежие новости, пробники и разборы заданий --> https://t.me/ege_oge_informatika