Информатика

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

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

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

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

Билл преподаёт химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что, вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильном уравнении химической реакции должно соблюдаться равенство).

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

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

Ещё более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать:

• <формула> ::= [<число>] <последовательность> {"+" [<число>] <последовательность>}
• <последовательность> ::= <элемент> [<число>] {<элемент> [<число>]}
• <элемент> ::= <химический элемент> | "(" <последовательность> ")"
• <химический элемент> ::= <прописная буква> [<строчная буква>]
• <прописная буква> ::= "A".."Z"
• <строчная буква> ::= "a".."z"
• <число> ::= "1".."9" {"0".."9"}

Будем говорить, что каждый отдельный химический элемент встречается в формуле всего X раз, если X - сумма всех различных вхождений этого химического элемента, умноженных на все числа, относящиеся к ним. Например, в формуле C2H5OH+3O2+3(SiO2)

• C встречается всего 2 раза;
• H встречается всего 6 раз (5 + 1);
• O встречается всего 13 раз; (1 + 3 * 2 + 3 * 2);
• Si встречается всего 3 раза.

Все множители в формулах - целые числа не меньше 2, если заданы явно, или равны 1 - по умолчанию.

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

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

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

<формула левой части>==<формула правой части>
если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:
<формула левой части>!=<формула правой части>
Здесь <формула левой части> должна быть замещена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а <формула правой части> - замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.

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

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

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

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

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

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

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки

10 * 1 * 50 + 50 * 20 * 5 + 10 * 50 * 5 = 500 + 5000 + 2500 = 8000.

Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким:

1 * 50 * 20 + 1 * 20 * 5 + 10 * 1 * 5 = 1000 + 100 + 50 = 1150.

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

Ограничения: 3 <= N <= 100, числа на картах целые от 1 до 100.

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

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

Ограничения: во входных данных числа вещественные и по модулю не превосходят 1000.

Входные данные
В первой строке находятся шесть вещественных чисел через пробел - координаты центров и радиусы двух кругов: x₁, y₁, r₁, x₂, y₂, r₂.

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

Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.

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

Входные данные
В первой строке записано слово S.

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

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

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