Задачи из книги "Олимпиадные задачи по программированию"
Ф. Меньшиков

Девятая тренировка

содержание задачника

Задача 9А. Диалог компьютеров

Три компьютера соединены сетью. Один из них — сервер, два других — клиенты. На сервере есть несколько файлов. Полные имена файлов, состоящие из двух частей (имя и расширение), различны. Оба клиента знают полные имена всех файлов, находящихся на сервере. Сервер выбирает один из своих файлов и посылает его имя одному из клиентов, а расширение — второму. Затем клиенты начинают общаться друг с другом, пытаясь определить, какой файл был выбран сервером (они хотят узнать полное имя файла). Однако клиенты вынуждены общаться очень ограниченным способом. Они по очереди посылают сообщения друг другу, но могут сказать только, что не знают полного имени файла. Если клиент не знает полного имени выбранного файла, он может послать другому клиенту сообщение, говорящее: «Я не знаю полного имени файла». Клиенты чередуются, посылая только это сообщение туда и обратно. Так продолжается до тех пор, пока один из клиентов не узнает полное имя файла или они не решат закончить диалог. Клиент, получивший первую часть полного имени файла, всегда ждет, что второй клиент пошлет первое сообщение.
Пусть вы знаете все полные имена файлов, находящихся на сервере, и слушаете разговор клиентов. Основываясь на этой беседе, вы должны определить набор файлов, которые могли быть выбраны сервером. Файлы в этом наборе называются файлами-кандидатами.
Ввод из файла dialogue.in. В первой строке находятся два целых числа, N и М, разделенные пробелом: N — число файлов на сервере, М — число сообщений, посланных клиентами, пытающимися определить полное имя файла.
Каждая из следующих N строк содержит одно полное имя файла. Полное имя файла дано в стиле, аналогичном формату 8.3 MS-DOS. Каждое полное имя представлено в форме имя. расширение, где и имя, и расширение состоят только из заглавных латинских букв и цифр. Имя всегда имеет от одного до восьми символов. Расширение имеет до трех символов и может быть пусто. Если расширение пусто, разделяющая точка может быть опущена.
Каждое полное имя файла появляется во входном файле не более одного раза.
Ограничения: 1 <$\le$ N$\le$ 1000, 1 $\le$ M$\le$ 100, время 3 с.

Вывод в файл dialogue.out. В первой строке выводится число файлов-кандидатов для данных набора файлов и числа сообщений между клиентами. Выводится 0, если файлы-кандидаты отсутствуют. В следующих строках находятся полные имена файлов-кандидатов, каждое в отдельной строке. Они должны идти в том же порядке и в том же написании, что и во входном файле. Это означает, что если разделяющая точка в названии конкретного файла была опущена во входном файле, то она должна быть опущена и в выводе, и наоборот. Файл нельзя упоминать более одного раза.
Пример
Ввод
19 2
LICENCE.TMP
WIN32.LOG
FILEID.
PSTOTEXT.TXT
GSVIEW32.EXE
GSVIEW32.IC0
GSVIEWDE.HLP
LICENCE
GSVIEWEN.HLP
GSVW32DE.DLL
FILEID.TMP
GSVW32EN.DLL
PST0TXT3.DLL
PST0TXT3.EXE
GSV16SPL.EXE
GVWGS32.EXE
ZLIB32.DLL
PRINTER.INI
README.TXT
Вывод
6
LICENCE.TMP
FILEID.
LICENCE
FILEID.TMP
PST0TXT3.DLL
PST0TXT3.EXE

Задача 9B. Бросание кубика

Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Найти вероятность того, что сумма выпавших чисел будет равна Q. Ограничения: 1 $\le$ N$\le$ 500, 1 $\le$ Q$\le$3000, время 1 с.
Ввод из файла die.in. В первой строке находятся числа N и Q через пробел.
Вывод в файл die.out. Выводится единственное вещественное число, которое должно отличаться от истинного значения не более чем на 0,01 истинного значения.
Примеры
Ввод
1 6
Вывод
0.16666

Задача 9С. Игра с монетами

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более К стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.
Ввод из файла coingame.in. В первой строке находится сначала число стопок N, за ним идут N чисел, задающих количество монет в стопках слева направо, а затем число К. Все числа в строке разделены пробелами. Ограничения: 1 $\le$N$\le$ 180, 1 $\le$K$\le$80, количество монет в стопке — не менее 1 и не более 20 000, время 1 с.
Вывод в файл coingame.out. Вывести одно число — максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.

Пример Ввод 3 4 9 1 3 Вывод 14

Задача 9D. Бассейн реки

Дана карта рек некоторого континента (смотрите рис). Каждая река показана как ломаная линия, которая начинается у истока реки и заканчивается или в точке, где река впадает в другую, или устьем реки. Вершины ломаной — или точки поворота реки, или точки впадения притоков. Будем рассматривать бассейн реки как выпуклый многоугольник минимальной площади, который содержит реку и все ее притоки. 

Примечание. Согласно этому определению бассейна реки одна и та же территория может принадлежать бассейнам различных рек.
Пример. Показан континент с тремя реками. Координаты рек и площади бассейнов даны в таблице.  Требуется найти максимальную площадь бассейна реки, расположенной на данном континенте. Ввод из файла basin.in. Первая строка содержит число рек N. В следующих строках файла содержится N блоков, описывающих реки.
Каждый блок номер i состоит:
• из одной строки с k_i — числом вершин ломаной, описывающей реку;
• k_i строк, содержащих пары вещественных чисел x_j и у_j (1 $\le$j$\le$k_i), разделенных пробелом, — координаты точек, описывающих реку.
Ограничения: 1$\le$N$\le$10, сумма k_i$\le$1000, -1000$\le$x_j, y_j$\le$1000, время 3 с. Вывод в файл basin.out. Вывести одно число — площадь наибольшего бассейна реки с двумя знаками после запятой.
Пример
Ввод
3
5
6 9
5 11
3 12
2 10
1 7
3
7 9
5 7
5 5.5
6
3 10
5 8
4 6
5 5.5
6 5
3 5
Вывод
16.00

Задача 9E. Ближайшее число

Дана матрица А размером NxN, заполненная неотрицательными целыми числами. Расстояние между двумя элементами A_ij и A_pq определено как |i - p| + |j - q|. Требуется заменить каждый нулевой элемент матрицы ближайшим ненулевым. Если есть две или больше ближайших ненулевых ячейки, нуль должен быть оставлен.
Ограничения: 1 $\le$ N$\le$ 200, 0 $\le$ A_ij $\le$1 000 000, время 3 с.
Ввод из файла neamum.in. В первой строке содержится число N. Затем идут N строк по N чисел, разделенных пробелами и представляющих собой матрицу. Вывод в файл nearnum.оut. Выводится N строк по N чисел, разделенных пробелами, — модифицированная матрица.
Пример
Ввод
3
0 0 0
1 0 2
0 3 0
Вывод
1 0 1
1 0 2
0 3 0

Задача 9F. Прямоугольное деление

Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить, на сколько частей эти прямоугольники разбивают плоскость (внутри частей не должно быть границ прямоугольников). Ввод из файла rectpart.in. В первой строке содержится число прямоугольников N. Далее идут N cтpoк, содержащих по четыре числа, x₁, y₁, x₂, y₂, - координаты двух противоположных углов прямоугольника.
Ограничения: 1 $\le$N$\le$ 100, координаты представляют собой целые числа и по абсолютной величине не превосходят 10 000, время 3 с.
Вывод в файл rectpart.out Вывести одно число — количество частей, на которые разбивается плоскость.
Пример
Ввод
3
10 20 50 30
40 10 50 25
40 25 80 30
Вывод
6

содержание задачника