Начало
Соревнования
Задачи очного тура личного первенства 1997 осень
1. Наибольший прямоугольник (5 баллов, только 1 курс)
Найти наибольший по площади белый прямоугольник в прямоугольнике из белых и черных клеток.
Ввод
Во входном файле в первой строке находятся два числа `m` и
`n` от 1 до 20. Далее идет `m` строк по `n` чисел. Число 1 представляет черную клетку, а 0 – белую.
Вывод
В выходной файл выводятся 4 числа – строка и колонка
для левого верхнего угла, затем ширина и высота найденного прямоугольника. Отчет номеров строк и колонок идет с 1.
Пример ввода
5 7 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0
Пример вывода
1 3 2 4
2. Обратно в число (10 баллов)
Для программы проверки корректности чеков и счетов может
потребоваться программа преобразования числа, записанного словами, обратно в число. Числа в диапазоне от 1 до 999999999.
Ввод
Во входном файле в первой строке содержится количество
тестов, далее идут строки (строчными буквами) длиной не более
100 символов, которые необходимо преобразовать.
Вывод
Для каждой теста из входного файла вывести соответствующее число. Если в порядке следования числительных имеется
ошибка, вывести кроме этого слово "ошибка". На склонение числительных (две тысяч, два тысячи) не обращать внимания.
Пример ввода
3 двести одиннадцать тысяч два один миллион одна тысяча сто двадцать семнадцать тысяч девятьсот девяносто девять миллионов
Пример вывода
211002 1001000 999137000 ошибка
Необходимый набор числительных: один (одна), два (две), три, четыре, пять, шесть, семь, восемь,
девять, десять, одиннадцать, двенадцать, тринадцать, четырнадцать,
пятнадцать, шестнадцать, семнадцать, восемнадцать, девятнадцать,
двадцать, тридцать, сорок, пятьдесят, шестьдесят, семьдесят,
восемьдесят, девяносто, сто, двести, триста, четыреста, пятьсот,
шестьсот, семьсот, восемьсот, девятьсот, тысяча (тысячи, тысяч),
миллион (миллиона, миллионов).
3. Умножение полиномов (20 баллов)
Ввод
Во входном файле находятся два полинома, по одному на
строке. Полином записан в виде:
[-][Коэф][x[Степ]]{(+|-)[Коэф][x[Степ]]}
Коэф – вещественное число
Степ – целое число
[…] – может отсутствовать
{…} – повторяется 0 или более раз
(+|-) – + или –
Длина записи полинома не превысит 100 символов, максимальная
степень полинома 20.
Вывод
В файле произведение введенных полиномов в том же виде.
Пример ввода
3x4-2.5x+1 -x+2
Пример вывода
-3x5+6x4+2.5x2-4x+2
от указанного и соответствовать возможностям языка по выводу вещественных чисел.
4. Анаграммы (15 баллов)
Напишите программу, генерирующую все возможные слова из
заданного набора букв. Некоторые буквы в наборе могут повторяться.
Пример: Из слова "aba" могут получиться следующие анаграммы: "aab","aba" и "baa"
Ввод
Во входном файле содержится слово до 30 букв, написанное
строчными бувами от a до z, из которого необходимо получить
анаграммы.
Вывод
В выходном файле должны получиться все возможные анаграммы введенного слова. Количество возможных анаграмм не будет превышать 10000.
Пример ввода
abca
Пример вывода
aabc aacb abac abca acab acba baac baca bcaa caab caba cbaa
5. Обедающие дипломаты (20 баллов)
Вы работаете в дипломатическом правительственном учреждении. Ваш начальник пригласил 9 дипломатов из различных стран
мира на торжественный обед и поручил вам найти, как рассадить
дипломатов за столом. Каждый дипломат знает от одного до пяти
языков. Чтобы говорить друг с другом, они должны знать какой-нибудь общий язык. Кроме того, если страны не поддерживают
дипломатические отношения, то дипломаты не будут говорить друг
с другом. Ваша задача – так разместить за обеденным столом вашего начальника и 9 дипломатов, чтобы каждый из них мог говорить со своими соседями слева и справа.
Обеденный стол круглый, на 10 человек. Ваш начальник будет сидеть на стуле №1. Остальные места нумеруются по часовой
стрелке с 2 до 10. Таким образом персона слева от начальника
сидит стуле №2, а справа – на стуле №10.
Соседи по столу должны говорить на общем языке. Персона
может говорить говорить с соседом слева на одном языке, а с
соседом справа на другом. Правительства гостей, сидящих на соседних местах, должны поддерживать дипломатические отношения
друг с другом.
Правительство вашего начальника, естественно, поддерживает дипломатические отношения с правительствами всех его гостей. Правительства гостей могут не иметь дипломатических отношений с правительствами всех других гостей.
Два дипломата из одной страны будут иметь дипломатические
отношения с одинаковым набором стран. Все страны всегда имеют
дипломатические отношения сами с собой. Дипломаты из одной
страны могут не говорить на общем языке (например, в Швейцарии
три официальных языка – французский, немецкий и итальянский).
Ввод
Во входном файле содержится список из 10 человек, по одному человеку на строку. Первая строка описывает вашего начальника, остальные – приглашенных дипломатов. Каждая строка
содержит несколько слов, разделенных одним пробелом. Каждое
слово состоит из прописных букв A-Z. Первое слово содержит 3
буквы и представляет собой код страны дипломата. Второе слово
содержит от 1 до 5 букв и указывает языки, на которых говорит
гость, по одной букве на язык. Далее идет набор до 9 трехбуквенных слов, представляющий коды стран, с которыми правительство гостя поддерживает дипломатические отношения.
Вывод
В выходном файле должна быть таблица рассадки гостей,
по одной строке на дипломата. В начале строки идет номер места, затем три слова, разделенных одним пробелом. Первое слово – это код языка для разговора с соседом слева. Второе слово – это код страны дипломата. Третье слово – это код языка для
разговора с соседом справа. Таблица должна печататься по по-
рядку мест от 1 до 10. Может существовать несколько решений,
но нужно вывести только одно. Если решений нет, вывести сообщение: NO SOLUTION EXISTS
Пример ввода
USA EF CHN GRB USR FRA FRG JPN ISR POR KOR CHN CFE USA GBR FRA FRG GBR ER USA CHN USR FRA FRG JPN ISR POR KOR USR RF USA GBR FRA FRG FRA F USA CHN GBR USR FRG JPN ISR POR FRG ERG USA CHN GBR USR FRA JPN ISR POR JPN JHG USA GBR FRA FRG JPN ISR POR KOR ISR HER USA GBR FRA FRG JPN KOR POR PGE USA GBR FRA FRG JPN KOR KEC USA GBR USR JPN ISR
Пример вывода
1 E USA E 2 E KOR E 3 E ISR H 4 H JPN G 5 G FRG G 6 G POR E 7 E GBR E 8 E USR F 9 F FRA F 10 F CHN E
6. Секретная переписка (30 баллов)
Два юных математика Сережа и Саша договорились о том, что
самую "секретную" информацию они будут зашифровывать следующим
образом. Каждое "секретное" слово они будут обозначать цепочкой слов той же длины (с тем же числом букв) и после двоеточия
цифрой указывать количество тех букв, которые в зашифрованном
и написанном слове стоят на одном и том же месте.
Например: последовательность БУК:2 СУК:2 ЛОМ:1 зашифровывает слово ЛУК.
Ввод
Во входном файле содержится несколько наборов тестов для
программы. В каждом тесте в первой строке указывается число
слов (≤20), шифрующих "секретное" слово. Последующие строки
содержат слова (прописными буквами) и после двоеточия количество тех букв, которые в зашифрованном и написанном слове стоят
на одном и том же месте. Набор тестов заканчивается 0. Длина
зашифрованного слова не превышает 10 букв, набор слов позволяет однозначно его определить (без использования словаря).
Вывод
На каждый тест в выходном файле должна быть
строка с расшифрованным словом.
Пример ввода
3 ВОЛ:2 ГАЗ:1 КОЛ:2 4 УРОД:2 ОВЦА:2 ОБОЗ:2 КРАН:0 0
Пример вывода
ГОЛ ОВОД
