1) Задача “Подбор кода”. (Автор — Брызгалов Е.В., оппонент — Деменев А.Г., 10 баллов.)
Группа Н-ских революционеров похитила с М-ской военной базы прототип экспериментальной нейтронной гранаты. Для активации взрывного механизма необходимо ввести код (последовательность из десятичных цифр). После подключения к гранате Н-ский эвристический анализатор частично расшифровал код, выдав строку-маску из N символов, каждый из которых имеет следующий смысл:
? — в этой позиции может находиться любая цифра;
заглавная латинская буква — в этой позиции может находиться любая цифра, но разным буквам соответствуют разные цифры, а одинаковым буквам — одинаковые цифры;
цифра — в этой позиции может находиться только эта цифра.
Требуется написать программу, которая определит число вариантов кода, удовлетворяющих строке-маске.
Примечания:
Технические требования
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Формат входных данных:
строка-маска, полученная на выходе Н-ского эвристического анализатора.
Формат выходных данных:
строка, содержащая число вариантов, удовлетворяющих строке-маске.
Пример файла входных данных:
?XX?XQ45Q
Пример файла выходных данных:
9000
2) Задача “Взрывоопасность”. (Идея — из материалов методической комиссии 1999-2000 уч.г., составитель — Брызгалов Е.В., оппонент — Шестаков А.П., 20 баллов.)
На одном из секретных заводов осуществляется обработка радиоактивных материалов, в результате которой образуются радиоактивные отходы двух типов: типа A — особо опасные и типа B — неопасные. Все отходы упаковываются в специальные прямоугольные контейнеры одинаковых размеров, после чего эти контейнеры укладываются в стопку (один над другим) для захоронения. Стопка является взрывоопасной, если в ней подряд идут более чем два контейнера с отходами типа A.
Требуется написать программу, которая подсчитывает количество возможных вариантов формирования взрывоопасной стопки для заданного числа контейнеров N.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Формат входных данных:
единственная строка входного файла содержит целое число N — количество контейнеров в стопке (1 <= N <= 31).
Формат выходных данных:
в единственной строке выходного файла должно содержаться искомое количество вариантов взрывоопасных стопок.
Пример файла входных данных:
4
Пример файла выходных данных (для приведенного выше входного файла):
3
3) Задача “Вирус”. (Автор — Брызгалов Е.В., оппонент — Шестаков А.П., 25 баллов.)
Колония клеток представляет собой квадратную матрицу порядка N (N < 500). В колонию проникает M (M < 11) вирусов, которые поражают клетки с координатами (X1, Y1), … (Xm, Ym). За одну единицу времени вирус проникает в клетки, соседние с зараженными (соседними считаются клетки, имеющие общую сторону).
Требуется написать программу, которая определит время заражения всей колонии.
Технические требования
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Формат входных данных:
1 строка — N
2 строка — M
3 строка — X1 Y1
4 строка — X2 Y2
…
M+2 строка — Xm Ym.
Формат выходных данных:
строка, содержащая одно число — время заражения.
Пример файла входных данных:
5
2
1 2
5 5
Пример файла выходных данных:
4
4) Задача “Анализ логических выражений”. (Автор — Еремин Е.А., оппонент — Брызгалов Е.В., 45 баллов.)
Рассматриваются логические выражения, записанные по следующим правилам:
а) логические значения "истина" и "ложь" записываются как TRUE и FALSE;
б) логические переменные обозначаются одной латинской буквой, первая — “A”, вторая — “B” и далее по алфавиту;
в) логические операции (в порядке убывания приоритета) имеют вид NOT, AND и OR; количество операций в выражении не превышает 8;
г) выражения, заключенные в скобки, выполняются в первую очередь согласно принятым в математике правилам; скобки могут быть вложенными (не более 4 одновременно открытых);
д) любое служебное слово отделяется от переменной как минимум одним пробелом; выделять пробелами скобки не обязательно;
е) ЗАГЛАВНЫЕ и строчные буквы не различаются. Например: A and (b OR c), то же самое, что и a and (b or c).
Требуется написать программу, которая должна вычислить введенную функцию для всех возможных (неповторяющихся) комбинаций значений аргументов и сосчитать, сколько раз при этом она принимает значение TRUE.
Примечание. Принять, что введенная запись логического выражения не содержит синтаксических ошибок.
Технические требования
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Формат входных данных:
Одна строка, содержащая логическое выражение.
Формат выходных данных:
Одна строка, содержащая число вариантов получения TRUE.
Пример файла входных данных:
(a and b) or not((b and c) or true)
Пример файла выходных данных:
2