SnarkNews winter series, round 5


Объём памяти, предоставляемый программе, составляет 64 Mb.

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

Три компьютера соединены сетью. Один из них - сервер, два других - клиенты. На сервере есть несколько файлов. Полные имена файлов, состоящие из двух частей (имя и расширение), различны. Оба клиента знают полные имена всех файлов, находящихся на сервере. Сервер выбирает один из своих файлов и посылает его имя одному из клиентов, а расширение - второму.

Затем клиенты начинают общаться друг с другом, пытаясь определить, какой файл был выбран сервером (они хотят узнать полное имя файла). Однако клиенты вынуждены общаться очень ограниченным способом. Они по очереди посылают сообщения друг другу, но могут сказать только, что не знают полного имени файла. Если клиент не знает полного имени выбранного файла, он может послать другому клиенту сообщение, говорящее: "Я не знаю полного имени файла". Клиенты чередуются, посылая только это сообщение туда и обратно. Так продолжается до тех пор, пока один из клиентов не узнает полное имя файла, или они не решат закончить диалог. Клиент, получивший первую часть полного имени файла, всегда ждёт, что второй клиент пошлёт первое сообщение.

Пусть Вы знаете все полные имена файлов, находящихся на сервере, и слушаете разговор клиентов. Основываясь на этой беседе, Вы должны определить набор файлов, которые могли быть выбраны сервером. Файлы в этом наборе называются файлами-кандидатами.

Ввод из файла dialogue.in. В первой строке находятся два целых числа, N и M, разделённые пробелом: N - число файлов на сервере, M - число сообщений, посланных клиентами, пытающимися определить полное имя файла.

Каждая из следующих N строк содержит одно полное имя файла. Полное имя файла дано в стиле, аналогичном формату 8.3 MS-DOS. Каждое полное имя представлено в форме имя.расширение, где и имя, и расширение состоит только из заглавных латинских букв и цифр. Имя всегда имеет от одного до восьми символов. Расширение имеет до трёх символов и может быть пусто. Если расширение пусто, разделяющая точка может быть опущена.

Каждое полное имя файла появляется во входном файле не более одного раза.

Ограничения: 1 <= N <= 1000, 1 <= M <= 100, время 3 с.

Вывод в файл dialogue.out. В первой строке выводится число файлов-кандидатов для данных набора файлов и числа сообщений между клиентами. Выводится 0, если файлы-кандидаты отсутствуют.

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

Примеры
Ввод 1
19 2
LICENCE.TMP
WIN32.LOG
FILEID.
PSTOTEXT.TXT
GSVIEW32.EXE
GSVIEW32.ICO
GSVIEWDE.HLP
LICENCE
GSVIEWEN.HLP
GSVW32DE.DLL
FILEID.TMP
GSVW32EN.DLL
PSTOTXT3.DLL
PSTOTXT3.EXE
GSV16SPL.EXE
GVWGS32.EXE
ZLIB32.DLL
PRINTER.INI
README.TXT
Вывод 1
6
LICENCE.TMP
FILEID.
LICENCE
FILEID.TMP
PSTOTXT3.DLL
PSTOTXT3.EXE

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

Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Найти вероятность того, что сумма выпавших чисел будет равна Q.
Ограничения: 1 <= N <= 500, 1 <= Q <= 3000, время 1 с.
Ввод из файла die.in. В первой строке находятся числа N и Q через пробел.
Вывод в файл die.out. Выводится единственное вещественное число, которое должно отличаться от истинного значения не более чем на 0.01 истинного значения.
Примеры
Ввод 1    Ввод 2    Ввод 3    Ввод 4
1 6       1 7       4 14      100 100
Вывод 1   Вывод 2   Вывод 3   Вывод 4
0.16666   0         0.11265   1.53e-78

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

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.
Ввод из файла coingame.in. В первой строке находится сначала число стопок N, за ним идут N чисел, задающих количество монет в стопках слева направо, а затем число K. Все числа в строке разделены пробелами.
Ограничения: 1 <= N <= 180, 1 <= K <= 80, количество монет в стопке - не менее 1 и не более 20 000, время 1 с.
Вывод в файл coingame.out. Вывести одно число - максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.
Примеры
Ввод 1          Ввод 2            Ввод 3
3  4 9 1  3     4  1 2 2 7  3     5  3 4 8 1 7  2
Вывод 1         Вывод 2           Вывод 3
14              5                 18

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

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

Будем рассматривать бассейн реки как выпуклый многоугольник минимальной площади, который содержит реку и все её притоки.

Примечание. Согласно этому определению бассейна реки, одна и та же территория может принадлежать бассейнам различных рек.

Пример. Показан континент с тремя реками. Координаты рек и площади бассейнов даны в таблице.
 Название реки     x       y     Площадь бассейна реки без притоков 
река 1 69 12,5
511
312
210
17
 
река 2 79 1,5
57
55,5
 
река 3 310 9,5
58
46
55,5
65
35
Требуется найти максимальную площадь бассейна реки, расположенной на данном континенте.
Ввод из файла basin.in. Первая строка содержит число рек N. В следующих строках файла содержится N блоков, описывающих реки.

Каждый блок номер i состоит: Ограничения: 1 <= N <= 10, сумма ki <= 1000, -1000 <= xjyj <= 1000, время 3 с.
Вывод в файл basin.out. Вывести одно число - площадь наибольшего бассейна реки с двумя знаками после запятой.
Примеры
Ввод 1    Ввод 2
3         2
5         5
6 9       6 9
5 11      5 11
3 12      3 12
2 10      2 10
1 7       1 7
3         6
7 9       3 10
5 7       5 8
5 5.5     4 6
6         5 5.5
3 10      6 5
5 8       3 5
4 6
5 5.5
6 5
3 5
Вывод 1   Вывод 2
16.00     12.50

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

Дана матрица A размером NxN, заполненная неотрицательными целыми числами. Расстояние между двумя элементами Ai j и Ap q определено как |i - p| + |j - q|.
Требуется заменить каждый нулевой элемент матрицы ближайшим ненулевым. Если есть две или больше ближайших ненулевых ячейки, нуль должен быть оставлен.
Ограничения: 1 <= N <= 200, 0 <= Ai j <= 1 000 000, время 1 с.
Ввод из файла nearnum.in. В первой строке содержится число N. Затем идут N строк по N чисел, разделённых пробелами и представляющих собой матрицу.
Вывод в файл nearnum.out. Выводится N строк по N чисел, разделённых пробелами, - модифицированная матрица.
Примеры
Ввод 1
3
0 0 0
1 0 2
0 3 0
Вывод 1
1 0 2
1 0 2
0 3 0

        Задача F. Анти-QuickSort

Для сортировки последовательности чисел широко используется быстрая сортировка - QuickSort. Далее приведена программа, которая сортирует массив a, используя этот алгоритм.
var
   a : array [1..N] of integer;

   procedure QSort(left, right : integer);
   var
      i, j : integer;
      key : integer;
      buf : integer;
   begin
      key := a[(left + right) div 2];
      i := left;
      j := right;
      repeat
         while a[i] < key do    {первый while}
            inc(i); 
         while key < a[j] do    {второй while}
            dec(j); 
         if i <= j then begin
            buf := a[i];
            a[i] := a[j];
            a[j] := buf;
            inc(i);
            dec(j);
         end;
      until i > j;

      if left < j then
         QSort(left, j);
      if i < right then
         QSort(i, right);
   end;

begin
   ...
   QSort(1, N);
end.
Хотя QuickSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго. Оценивать время работы алгоритма будем количеством сравнений с элементами массива (то есть суммарным количеством сравнений в первом и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
Ввод из файла antiqs.in. В первой строке находится единственное число N.
Ограничения: 1 <= N <= 70 000, время 1 с.
Вывод в файл antiqs.out. Вывести перестановку чисел от 1 до N, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.
Примеры
Ввод 1
3
Вывод 1
1 3 2