Задачи командных соревнований областной олимпиады школьников по информатике 2006

В тридевятом царстве, в тридевятом государстве между двумя любыми городами есть дорога, но только в одну сторону. Местонахождение резиденции царя держится в секрете, но известно, что в столичный город можно попасть из любого другого города, проезжая не более чем через один промежуточный город.

Напишите программу, которая определит местонахождение столицы по информации о дорогах страны.

В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество городов. Далее следует `(N-1)` строка, содержащих только символы + (плюс) и – (минус). Длина `i`-й строки равна `i-1`. `j`-й символ в `i`-й строке показывает направление дороги: + означает, что дорога ведет из города `j` в город `i`;  – означает, что дорога ведет из города `i` в город `j`.

В выходной файл в первой строке вывести количество городов-кандидатов для местонахождения столицы, а во второй строке – номера городов-кандидатов в порядке возрастания, разделяя их пробелами.

4
+
-+
+-+

3
2 3 4

В пруд выпустили `N` щук. Щука сыта, если она съела `K` других щук. При подсчете количества съеденных щук не учитывается, сколько каждая из них съела щук до того, как её съели.

Напишите программу, которая вычислит, какое максимальное число щук сможет насытиться. Съеденные сытые щуки при подсчете учитываются как сытые. Например, пусть `N=3`, а `K=1`, тогда насытиться смогут 2 щуки, но одна из них будет сама съедена сразу после обеда.

В первой строке входного файла содержатся два целых числа, разделенных пробелом – первоначальное количество щук в пруду `N` (`1\ ≤\ N\ ≤\ 1000`) и количество щук для насыщения `K` (`1\ ≤\ K\ ≤\ 100`).

В первой строке выходного файла вывести одно целое число – максимальное количество насытившихся щук.

30 3

9

Целое число `N\ ≥\ 10` в десятичном представлении обладает свойством вычеркиваемости, если при вычеркивании любой цифры числа результат делится на вычеркнутую цифру без остатка. Очевидно, это число не может содержать цифры 0, так как на 0 делить нельзя.

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

В первой строке входного файла содержится одно целое число `M` (`10\ ≤\ M\ ≤\ 10^9`).

В выходной файл вывести одно целое число – минимальное число `N\ ≥\ M`, обладающее свойством вычеркиваемости.

113

122

В клетках таблицы `N`x`N` расставлены знаки + и -. Разрешается одновременно заменить знаки на противоположные во всех клетках некоторой строки или некоторого столбца. Это действие можно повторять несколько раз. Требуется минимизировать число минусов в таблице.

Напишите программу, которая определит для заданной таблицы, какого наименьшего числа минусов можно добиться.

В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 20`) – размеры таблицы. Далее следует `N` строк, содержащих по `N` символов '+' и '-'.

В выходной файл одно целое число – минимальное число минусов, которое можно получить в головоломке.

3
+-+
---
+-+

1

В компании ACM (All Cutting Machine) была разработана программа для составления карт раскроя листов на прямоугольные части без отходов. Но оказалось, что не все карты раскроя могут быть применены практически, так как резательная машина может выполнять только операцию разрезания прямоугольной заготовки на два прямоугольника.

Напишите программу, которая проверяет выполнимость карты раскроя.

Во входном файле содержится до 10 карт раскроя для проверки. Каждая карта начинается со строки, содержащей два целых числа, разделенных пробелом – размеры листа `H` и `W` (`0\ <\ H\ ≤\ 20`, `0\ <\ W\ ≤\ 20`). Далее следует `H` строк по `W` символов – собственно карта раскроя, каждый символ соответствует квадрату единичного размера. Одинаковые буквы означают части одной прямоугольной детали; разные детали обозначены различными латинскими буквами. Регистр букв существенен. Ввод завершается строкой с 0 0, которая не обрабатывается.

В выходной файл для каждой карты раскроя вывести на соответствующей строке сообщение "YES" или "NO" в зависимости от ее применимости.

3 3
ABB
ACD
EED
2 4
AAAB
CCDD
0 0

NO
YES

Имеется последовательность дат каких-то событий в хронологическом (возрастающем) порядке, произошедших в период с 1 января 1901 до 31 декабря 1999. Все даты были записаны в одинаковом, но неизвестном формате. Существуют шесть возможных форматов записи даты:

Здесь `"dd"` означает номер дня, `"mm"` – номер месяца, `"yy"` – две последние цифры года. Все числа двухзначные с ведущим 0 при необходимости.

Напишите программу, которая проверит корректность хронологии и определит формат записи для заданной последовательности дат.

В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 100`). Далее следует `N` строк, в каждой строке дата в формате 99/99/99.

В выходной файл вывести одно целое число – номер формата записи даты, если его удалось определить однозначно, либо число 7, если существует несколько вариантов, либо число 0, если ни один из вариантов формата не подошел.

2
31/01/01
01/12/99

1

По результатам исследований Кембриджского университета, не имеет значения, в каком порядке расположены буквы в слове. Главное, чтобы первая и последняя буквы были на месте. Остальные буквы могут следовать в полном беспорядке, всё равно текст читается без проблем. Причиной этого является то, что мы читаем не каждую букву по отдельности, а всё слово целиком. Данную технологию решили взять на вооружения спамеры, чтобы их рекламные сообщения могли проходить через антиспамовые фильтры.

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

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

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

по результатам исследований
одного английского университета

по рзельуататм илессодавинй
оногдо агнийлксгоо уиневертитса

Для распространения сигнала спутникового телевидения фирма установила в городе антенны, принимающие передачу в цифровом виде со спутника и ретранслирующие его в виде обычного телесигнала. Радиоволны плохо проходят через бетон, поэтому хотя фирма и установила передающие антенны на достаточно высоких зданиях, некоторые дома оказались в "тени" более высоких зданий и таким образом вне зоны приема. Чтобы в доме могли смотреть телепередачи, нужно установить на крыше здания приемную антенну такой высоты, чтобы она находилась на прямой линии, не перекрываемой другими зданиями, хотя бы с одной из передающих антенн.

Напишите программу, которая вычислит минимальные высоты приемных антенн для всех зданий города.

В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 10`) – количество передающих антенн. Далее следует `N` строк, содержащих по два целых числа, разделенных пробелом – координата и высота `i`-й передающей антенны. Следующая строка содержит число `M` (`1\ ≤\ M\ ≤\ 100`) – количество зданий. Далее следует `M` строк, содержащих по два целых числа, разделенных пробелом – координата и высота `j`-го здания. Все координаты различны и находятся в интервале от 0 до `10^5`. Высоты антенн и зданий находятся в диапазоне от 1 до 1000.

В выходной файл вывести `M` строк, содержащих по одному числу. В `j`-ой строке выводится минимальная высота приемной антенны на `j`-м здании с точностью `10^{-2}`.

2
0 200
500 150
4
100 150
200 60
300 150
400 60

0.00
40.00
0.00
0.00