Информатика

На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен чёрно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади - точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали.

.***..***
.*.*.**.*
.***.*.**
*...**.*.

На схеме три куска - один без дыр, а два - с одной дырой каждый: первый площадью 8, второй - площадью 12.
Ваша цель - найти кусок с наибольшим количеством дыр в нём. Дыра - это 4-связная область точек, полностью окружённых символами *. Если несколько кусков имеют одинаковое количество дыр, нужно выбрать кусок минимальной площади.

Входные данные
В первой строке содержатся два числа W и H, разделённые пробелами. Следующие H строк содержат по W символов каждая. Символы в этих строках - или * (ASCII 42), или точка (ASCII 46).

Ограничения: 1 <= W, H <= 100.

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

Пещера представлена кубом, разбитым на N частей по каждому измерению (то есть на N 3 кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.

Ограничения: 1 <= N <= 30.

Входные данные
В первой строке содержится число N. Далее следует N блоков. Блок состоит из пустой строки и N строк по N символов: # - обозначает клетку, заполненную камнями, точка - свободную клетку. Начальное положение спелеолога обозначено заглавной буквой S. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.

Выходные данные
Вывести одно число - длину пути до поверхности.

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

Ограничения: 3 <= N <= 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000.

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

Выходные данные
Вывести одно число - количество точек с целочисленными координатами на границе многоугольника.

Бумажная полоска разделена на N клеток. Двое играющих по очереди выбирают и зачёркивают ровно K пустых смежных клеток. Выигрывает сделавший последний ход. Оба игрока придерживаются правильной стратегии. Дана ситуация игры. Требуется определить, кто выиграет.

Входные данные
Ограничения: 1 <= K <= N <= 40.

В первой строке содержатся числа N и K, во второй строке N символов: латинская заглавная O - пустая клетка, латинская заглавная X - зачёркнутая клетка.

Выходные данные
Вывести одно число: 1, если выиграет первый, сделавший ход; 2, если выиграет второй; 0, если ход сделать нельзя.

Для сортировки последовательности чисел широко используется быстрая сортировка - 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). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.

Входные данные
В первой строке находится единственное число N.

Ограничения: 1 <= N <= 70 000.

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

Дана матрица A размером N*N, заполненная неотрицательными целыми числами. Расстояние между двумя элементами A_{i j} и A_{p q} определено как |i - p| + |j - q|.

Требуется заменить каждый нулевой элемент матрицы ближайшим ненулевым. Если есть две или больше ближайших ненулевых ячейки, нуль должен быть оставлен.

Ограничения: 1 <= N <= 200, 0 <= A_{i j} <= 1 000 000.

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

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

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

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

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

Пример. Показан континент с тремя реками. Координаты рек и площади бассейнов даны в таблице.


 

Название реки	x	y	Площадь бассейна реки без притоков
река 1	6	9	12,5
	5	11
	3	12
	2	10
	1	7
река 2	7	9	1,5
	5	7
	5	5,5
река 3	3	10	9,5
	5	8
	4	6
	5	5,5
	6	5
	3	5

Требуется найти максимальную площадь бассейна реки, расположенной на данном континенте.

Входные данные
Первая строка содержит число рек N. В следующих строках файла содержится N блоков, описывающих реки.

Каждый блок номер i состоит:

из одной строки с k_i - числом вершин ломаной, представляющей реку;
ki строк, содержащих пары вещественных чисел x_j и y_j (1 <= j <= k_i), разделённых пробелом, - координаты точек, описывающих реку.
Ограничения: 1 <= N <= 10, сумма k_i <= 1000, -1000 <= x_j, y_j <= 1000.

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

Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Найти вероятность того, что сумма выпавших чисел будет равна Q.

Ограничения: 1 <= N <= 500, 1 <= Q <= 3000.

Входные данные
В первой строке находятся числа N и Q через пробел.

Выходные данные
Выводится единственное вещественное число, которое должно отличаться от истинного значения не более чем на 0.01 истинного значения.

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

Входные данные
В первой строке задано число N. В следующих N строках содержится по N символов. Символом # обозначена вырезанная клетка, точкой - невырезанная клетка, @ - заданные клетки (таких символов два). 2 <= N <= 50.

Выходные данные
Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом @.

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

Входные данные
В первой строке находится число R, во второй строке заданы широта и долгота первой точки, в третьей строке - широта и долгота второй точки. Широта в градусах от -90 до 90, долгота в градусах от -180 до 180, 100 <= R <= 10 000, все числа вещественные.

Выходные данные
Вывести длину пути с двумя знаками после запятой.

Игра для двух игроков определяется её деревом. Соперники делают ходы по очереди. Первый игрок начинает игру. Игра кончается или вничью, или победой одного из игроков. Листья дерева этой игры могут иметь значения, равные одному из трёх чисел: +1 - победа первого игрока, -1 - победа второго игрока, 0 - ничья. Ваша задача - определить, кто выиграет, если оба противника следуют правильной стратегии.

Входные данные
Узлы дерева пронумерованы последовательными целыми числами. Корень дерева всегда имеет номер 1. Первая строка входного файла содержит целое N - число узлов в дереве игры. Следующая N - 1 строка описывает узлы - одна строка для каждого узла (за исключением первого). Вторая строка содержит описание второго узла дерева, третья - третьего узла и т.д. Если узел является листом, первый символ строки - L, затем идёт пробел, затем номер родительского узла, ещё пробел и результат игры (+1 - победа первого игрока, -1 - победа второго, 0 - ничья). Если узел внутренний, то строка содержит N - первый символ, затем пробел и номер родительского узла. 2 <= N <= 1000.

Выходные данные
Выводится +1, если выигрывает первый игрок, -1, если второй, и 0 - в случае ничейного исхода.

Даны N натуральных чисел. Найти минимальное натуральное число, не представимое суммой никаких из этих чисел, если в эту сумму каждое исходное число может входить не более одного раза.
(1 <= N <= 10 000, значения исходных чисел от 1 до 1 000 000 000.)

Входные данные
В первой строке находится число N, в следующих N строках - по одному натуральному числу.

Выходные данные
Вывести одно число.

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

Входные данные
В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика. 2 <= N <= 250.

Выходные данные
В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов - как и на вводе, но X, а также все точки по пути заменяются плюсами +.

В прямоугольной декартовой системе координат прямая задана двумя принадлежащими ей точками (0, W) и (100N, E). Также заданы N2 квадратов со сторонами, параллельными осям координат. Квадрат S_i, j имеет координаты углов (100i, 100j) и (100i - 100, 100j - 100), i, j = 1, 2, ..., N. Требуется найти количество квадратов, имеющих общую точку с прямой.

Входные данные
В первой строке находятся три целых числа, N, W и E, разделённых пробелами. 1 <= N <= 100, 0 <= W, E <= 100N, все числа целые.

Выходные данные
Вывести одно число - количество квадратов.

Слава и Оля играют в игру умножения - умножают целое число P на одно из чисел от 2 до 9. Слава всегда начинает с P = 1, делает умножение, затем число умножает Оля, затем Слава и т.д. Перед началом игры им задают случайное число N, и победителем считается тот, кто первым получит P >= N. Определить, кто выиграет при заданном N, если оба играют наилучшим образом.

Входные данные
В первой строке находится единственное число N. 2 <= N <= 4 294 967 295.

Выходные данные
Выводится одна строка - "Stan wins.", если победит Слава, или "Ollie wins.", если победит Оля.

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А - 1, Б - 2, ..., Я - 33), а пробел - нулем. Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.

Входные данные
В первой строке содержится последовательность цифр. Цифр не более 100.

Выходные данные
Вывести одно число.

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



Входные данные
В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решётка - сегмент со стеной. 3 <= N <= 33, размер сегмента 3 x 3 м, высота стен 3 м.

Выходные данные
Вывести одно число - площадь видимой части внутренних стен лабиринта в квадратных метрах.

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

Входные данные
В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика. 2 <= N <= 40.

Выходные данные
В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов - как и на вводе, но буква X, а также все точки по пути заменяются плюсами.

Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить площадь фигуры, образованной объединением данных прямоугольников.

Входные данные
В первой строке находится число прямоугольников - N. Затем идут N строк, содержащих по 4 числа: x₁, y₁, x₂, y₂ - координаты двух противоположных углов прямоугольника. 1 <= N <= 100, координаты целые и по абсолютному значению не превосходят 10 000.

Выходные данные
Вывести одно число - площадь фигуры.

Дано N целых чисел A₁, A₂, ..., A_N. Требуется найти количество различных значений сумм вида k₁A₁ + k₂A₂ + ... + k_NA_N.
(1 <= N <= 500, 0 <= Ai <= 100, 0 <= k_i <= 1, все числа целые.)

Входные данные:
В первой строке находится число N, во второй - A₁, A₂, ..., A_N через пробел.

Выходные данные: 
Вывести одно число - количество различных значений сумм.