Задача N1. Наибольший прямоугольник (5 баллов) (только 1 курс)
(источник: Арсак Ж. Программирование игр и головоломок)
Найти наибольший по площади белый прямоугольник в прямо-
угольнике из белых и черных клеток.
Вход:
В файле INPUT.DAT в первой строке находятся два числа m и
n от 1 до 20. Далее идет m строк по n чисел. Число 1 представ-
ляет черную клетку, а 0 - белую.
Выход:
В файл OUTPUT.DAT выводятся 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
Т.е. наибольший белый прямоугольник имеет размер 2x4 и
находится в 1 строке 3 колонке.
--------------------------------------------------------------
Задача N2. Обратно в число (рейтинг 10 баллов)
Для программы проверки корректности чеков и счетов может
потребоваться программа преобразования числа, записанного сло-
вами, обратно в число. Числа в диапазоне от 1 до 999999999.
Вход:
В файле INPUT.DAT в первой строке содержится количество
тестов, далее идут строки (строчными буквами) длиной не более
100 символов, которые необходимо преобразовать.
Выход:
Для каждой теста из входного файла вывести соответству-
ющее число. Если в порядке следования числительных имеется
ошибка, вывести кроме этого слово "ошибка". На склонение чис-
лительных (две тысяч, два тысячи) не обращать внимания.
Пример ввода:
3
двести одиннадцать тысяч два
один миллион одна тысяча
сто двадцать семнадцать тысяч девятьсот девяносто девять миллионов
Пример вывода:
211002
1001000
999137000 ошибка
Необходимый набор числительных:
один (одна), два (две), три, четыре, пять, шесть, семь, восемь,
девять, десять, одиннадцать, двенадцать, тринадцать, четырнадцать,
пятнадцать, шестнадцать, семнадцать, восемнадцать, девятнадцать,
двадцать, тридцать, сорок, пятьдесят, шестьдесят, семьдесят,
восемьдесят, девяносто, сто, двести, триста, четыреста, пятьсот,
шестьсот, семьсот, восемьсот, девятьсот, тысяча (тысячи, тысяч),
миллион (миллиона, миллионов)
--------------------------------------------------------------
Задача N3. Умножение полиномов (рейтинг 20 баллов)
Вход:
В файле INPUT.DAT находятся два полинома, по одному на
строке. Полином записан в виде:
[-][Коэф][x[Степ]](+|-)[Коэф][x[Степ]]
Коэф - вещественное число
Степ - целое число
[...] - может отсутствовать
... - повторяется 0 или более раз
(+|-) - + или -
Длина записи полинома не превысит 100 символов, максимальная
степень полинома 20.
Выход:
В файле OUTPUT.DAT произведение введенных полиномов в том же виде.
Пример ввода:
3x4-2.5x+1
-x+2
Пример вывода:
-3x5+6x4+2.5x2-4x+2
Вывод коэффициентов отличных от 0 и 1, может отличаться
от указанного и соответствать возможностям языка по выводу ве-
щественных чисел.
--------------------------------------------------------------
Задача N4. Анаграммы (рейтинг 15 баллов) ACM195
Напишите программу, генерирующую все возможные слова из
заданного набора букв. Некоторые буквы в наборе могут повто-
ряться.
Пример: Из слова "aba" могут получиться следующие анаг-
раммы: "aab","aba" и "baa"
Вход:
В файле INPUT.DAT содержится слово до 30 букв, написанное
строчными бувами от a до z, из которого необходимо получить
анаграммы.
Выход:
В файле OUTPUT.DAT должны получиться все возможные анаг-
раммы введенного слова. Колисчество возможных анаграмм не бу-
дет превышать 10000.
Пример ввода:
abca
Пример вывода:
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
Примечание: генерация (без сортировки и хранения сгенери-
рованных анаграмм!) анаграмм в алфавитном порядке +5 баллов
--------------------------------------------------------------
Задача N5. Обедающие дипломаты (рейтинг 20 баллов) ACM265
Вы работаете в дипломатическом правительственном учрежде-
нии. Ваш начальник пригласил 9 дипломатов из различных стран
мира на торжественный обед и поручил вам найти, как рассадить
дипломатов за столом. Каждый дипломат знает от одного до пяти
языков. Чтобы говорить друг с другом, они должны знать ка-
кой-нибудь общий язык. Кроме того, если страны не поддерживают
дипломатические отношения, то дипломаты не будут говорить друг
с другом. Ваша задача - так разместить за обеденным столом ва-
шего начальника и 9 дипломатов, чтобы каждый из них мог гово-
рить со своими соседями слева и справа.
Обеденный стол круглый, на 10 человек. Ваш начальник бу-
дет сидеть на стуле N1. Остальные места нумеруются по часовой
стрелке с 2 до 10. Таким образом персона слева от начальника
сидит стуле N2, а справа - на стуле N10.
Соседи по столу должны говорить на общем языке. Персона
может говорить говорить с соседом слева на одном языке, а с
соседом справа на другом. Правительства гостей, сидящих на со-
седних местах, должны поддерживать дипломатические отношения
друг с другом.
Правительство вашего начальника, естественно, поддержива-
ет дипломатические отношения с правительствами всех его гос-
тей. Правительства гостей могут не иметь дипломатических отно-
шений с правительствами всех других гостей.
Два дипломата из одной страны будут иметь дипломатические
отношения с одинакомым набором стран. Все страны всегда имеют
дипломатические отношения сами с собой. Дипломаты из одной
страны могут не говорить на общем языке (например, в Швейцарии
три официальных языка - французский, немецкий и итальянский).
Вход:
В файле INPUT.DAT содержится список из 10 человек, по од-
ному человеку на строку. Первая строка описывает вашего на-
чальника, остальные - приглашенных дипломатов. Каждая строка
содержит несколько слов, разделенных одним пробелом. Каждое
слово состоит из прописных букв A-Z. Первое слово содержит 3
буквы и представляет собой код страны дипломата. Второе слово
содержит от 1 до 5 букв и указывает языки, на которых говорит
гость, по одной букве на язык. Далее идет набор до 9 трехбук-
венных слов, представляющий коды стран, с которыми правитель-
ство гостя поддерживает дипломатические отношения.
Выход:
В файле OUTPUT.DAT должна быть таблица рассадки гостей,
по одной строке на дипломата. В начале строки идет номер мес-
та, затем три слова, разделенных одним пробелом. Первое слово
- это код языка для разговора с соседом слева. Второе слово -
это код страны дипломата. Третье слово - это код языка для
разговора с соседом справа. Таблица должна печататься по по-
рядку мест от 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
--------------------------------------------------------------
Задача N6. Секретная переписка (рейтинг 30 баллов)
(источник: Олимпиада по информатике 5 класс от 9.9.97)
Два юных математика Сережа и Саша договорились о том, что
самую "секретную" информацию они будут зашифровывать следующим
образом. Каждое "секретное" слово они будут обозначать цепоч-
кой слов той же длины (с тем же числом букв) и после двоеточия
цифрой указывать количество тех букв, которые в зашифрованном
и написанном слове стоят на одном и том же месте.
Например: последовательность БУК:2 СУК:2 ЛОМ:1 зашифровы-
вает слово ЛУК.
Вход:
В файле INPUT.DAT содержится несколько наборов тестов для
программы. В каждом тесте в первой строке указывается число
слов (<=20), шифрующих "секретное" слово. Последующие строки
содержат слова (прописными буквами) и после двоеточия количес-
тво тех букв, которые в зашифрованном и написанном слове стоят
на одном и том же месте. Набор тестов заканчивается 0. Длина
зашифрованного слова не превышает 10 букв, набор слов позволя-
ет однозначно его определить (без использования словаря).
Выход:
На каждый тест в выходном файле OUTPUT.DAT должна быть
строка с расшифрованным словом.
Пример ввода:
3
ВОЛ:2
ГАЗ:1
КОЛ:2
4
УРОД:2
ОВЦА:2
ОБОЗ:2
КРАН:0
0
Пример вывода:
ГОЛ
ОВОД