Problem A. Smooth convex hull

Author:T. Chistyakov, A. Klenin   Time limit:3 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

There are N points on a plane. Convex hull is such a convex polygon with the least possible area, that all the given points are either within its interior or belong to its border.

Let's say that one convex polygon is smoother that the other one if it's sharpest angle is more obtuse than the sharpest angle of the other one.

Your task is to make the convex hull of the given set of points as smooth as possible. To do it you are allowed to exclude no more than one point from the given set.

Input file format

Input file contains integer N, then N pairs of real numbers xi yi describing given points. There are no duplicate points in the input file.

Output file format

Output file must contain a single number: the sharpest angle (in radians) in the most smooth convex hull with absolute error less than 0.01.

Constraints

3 ≤ N ≤ 1000

1 ≤ xi, yi ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5
1 1  2 10  1 3  3 1  3 3 
1.57
2
4
1 1  1 3  3 1  3 3 
1.57

Задача B. Выпуклая оболочка

Автор:Восьмая всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:convex.in   Ограничение памяти:256 Мб
Выходной файл:convex.out  

Условие

Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит также и отрезок, соединяющий эти точки. Минимальное по включению множество, содержащее заданное множество точек X, называется выпуклой оболочкой множества X.

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.

Формат входного файла

Первая строка входного файла содержит число n — количество углов. Каждая из следующих n строк описывает углы. Каждый угол описывается координатами трех точек: вершины и двух отличных от вершины точек — по одной на каждом из лучей.

Формат выходного файла

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

На первой строке выведите l — количество объектов в ответе. Следующие l строк должны со- держать описание объектов. Объекты описываются следующим образом:

Если выпуклой оболочкой является вся плоскость, то выведите l = 0.

Ограничения

1 ≤ n ≤ 1000

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

Примеры тестов

Входной файл (convex.in) Выходной файл (convex.out)
1
2
3 1 4 1 4 4
2 2 4 3 3 4
3
inray 4 1 3 1
segment 3 1 2 2
outray 2 2 3 5
2
2
0 0 1 0 0 1
0 0 -1 0 0 1
1
line 1 0 -1 0
3
2
0 0 1 0 0 1
0 0 -1 0 0 -1
0

Problem C. Knuth-Morris-Pratt

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

Constraints

Length of each string does not exceed 100000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16

Problem L. Improve RLE

Author:I. Ludov, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

A computer programmer and mathematician Kumar Harikrishnan develops a new data compression system — ACM (Advanced Compression Method) — which will incorporate all of his brilliant ideas.

The first component of ACM will be a modification of well-known RLE algorithm, called Improved RLE. Since Kumar have much more difficult tasks to accomplish (such as to write Improved Hamming and Improved Lempel-Ziv), he asks you to implement this simple, yet important part of a system.

An algorithm should replace repeating substrings of source string with a single instance of substring concatenated with the number of repetitions. If some substring should not be repeated, it is concatenated with number 1.

Your program must find the shortest possible compression of the given string.

Input file format

A single line of input file contains the string to be compressed. It may contain spaces, but does not contain digits as Kumar has invented a complex digit-escaping system to prevent uncompressing ambiguity.

Output file format

Output file must contain minimal length compression of the source string. There should be no extra whitespace characters before or after the string.

Constraints

Length of the source string is from 1 to 1000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
aaaaaaaaaa
a10
2
a c c c
a1 c3
3
abc
abc1

Problem M. Fool Game

Author:Far-Eastern Subregional   Time limit:3 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

The game of fool is played with a small set of cards, which includes nine ranks - 6, 7, 8, 9, 0 (10), J (Jack), Q (Queen), K (King), A (Ace) of the four suits each - h (Hearts), s (Spades), d (Diamonds) and c (Crosses). So, for example a queen of spades is denoted Qs, and a ten of diamonds is 0d. One of the suits is declared a trump. During the game, the card beats another card, if either it has the same suit and higher rank, or it is a trump, while the beaten card is not.

In the game, a move proceeds as following. First player puts one of his cards on the desk, and the second player can either beat it with one of his cards, putting his card over it, or take it, if he has no suitable card. If the card is beaten, first player may flip in any of his remaining cards, which has same rank as any card already on the desk. This card, in turn, may be beaten or taken together with all other cards on the desk, etc. For example, if first player has cards 6s6dQhKd, the second player has 6h7h0sQd and hearts are the trumps, then first player can move with Kd, which is beaten with 6h, then flip in 6s, beaten by 0s, then 6d, beaten by Qd and at last Qh, which can not be beaten with 7h, so the second player has to take it.

Your task is to write a program that, given the trump suit and first and second playerTs cards, determines for the first player such a move as to eventually make the second player take.

Your task is to write a program that, given the trump suit and first and second playerTs cards, determines for the first player such a move as to eventually make the second player take.

If there is more than one such move, the program must find one with smallest rank. If there is several moves with smallest rank, program must choose the card with the first suit in the order mentioned in the first paragraph (i.e. h < s < d < c). In the example above, second player could beat Kd with 7h, thus preventing further flips. On the other hand, move of Qh will be immediately taken.

Input file format

In the first line of input file there is a single character h, s, d, or c, determining a trump suit. On the second line there is a string denoting first playerTs cards, and on the third line S the string with the second playerTs cards. All cards are different, and the players have equal number of cards.

Output file format

Output file must contain a single line with either a card to move or a string "NO", if a program was unable to find it.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
s
As7h8dJc
Jd8s7c0c
7h

Задача N. Заколдованный аквариум

Автор:И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

По мотивам романа А. и Б. Стругацких “Понедельник начинается в субботу”.

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

 — Подождите, остановил его речь Выбегалло, вот закончим проверку и выключим воду.

 — Да какая же это проверка, это же чистой воды саботаж! — возмущался Хунта, вот сейчас заделаю все дырки в вашем аквариуме, и тогда будем разговаривать.

 — Нет, это категорически невозможно! — Возражал Выбегалло, — как вы себе это представляете? Мы проводим важнейший эксперимент!

 — Может быть, объясните, что здесь все-таки происходит? - вмешался в разговор Привалов

 — Позвольте, я объясню, начал было Выбегалло, но Кристобаль Хозевич не дал ему закончить, и, сделав руками несколько пассов, произнес, — вот теперь порядок, ничего не вливается и не выливается, можете объяснять.

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

Привалов, наконец, осмотрел новый аквариум. Он представлял собой прямоугольный параллелепипед размерами W × H × L метров без верхней крышки, на лицевой стороне которого было вырезано N квадратных отверстий c длиной стороны ai метров. Сверху над аквариумом висела большая труба, через которую в него поступало M кубических метров воды в секунду.

 — Так вот, — продолжил Выбегалло, — до появления здесь Кристобаля Хозевича мы проводили эксперимент, целью которого было определить уровень воды в этом аквариуме при заданной конфигурации отверстий.

 — А более сухого способа вы не нашли, — вставил свою реплику Хунта

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

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

Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме. Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой: через отверстие площадью b квадратных метров в одну секунду будет вытекать V × b кубических метров воды.

В начале эксперимента аквариум пуст. Через некоторое время после того, как из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется (либо аквариум переполнится). Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.

Формат входного файла

Входной файл содержит числа V M N — соответственно скорость вытекания воды (в м / с), поток втекающей воды (м3 / c) и количество отверстий в лицевой стороне аквариума. Далее следует N троек чисел xi yi ai — координаты нижнего левого угла и длина стороны. отверстия номер i. Отверстия не пересекаются и не соприкасаются друг с другом.

Формат выходного файла

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

Ограничения

0 < V, M ≤ 1000, 0 ≤ N ≤ 100, 0 ≤ xi, yi, ai ≤ 106.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 4 3
1.0 1.0 4.0
6.0 2.0 4.0
11 5.0 3.0
2.0

Задача O. Разрезанная рамка

Автор:А. Кленин   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Прямоугольная рамка была разрезана на N кусков. Каждый кусок может представлять собой либо отрезок прямой, либо "уголок" — два отрезка, соединённых под прямым углом.

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

Формат входного файла

Входной файл содержит число кусков N, за которым следуют N пар целых чисел ai bi, описывающих длину двух отрезков "уголка" i-го куска. Если кусок является отрезком, то ai = 0 либо bi = 0.

Формат выходного файла

Выходной файл должен содержать два положительных целых числа W H — ширину и высоту рамки, при этом W ≥ H. Если решения не существует, следует выдать число  − 1. Если решений несколько, следует выдать решение с максимальным значением W.

Ограничения

1 ≤ N ≤ 10, 0 ≤ ai, bi ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10
1 1  1 1
1 0  1 0  1 0  1 0
0 2  0 2  0 2  0 2
7 1
2
5
1 1  1 1  1 1  1 1  5 0
-1

Задача P. Небезопасное пересечение дороги

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Пешеход переходит дорогу, состоящую из K полос автомобильного движения. Он заметил N автомобилей, каждый из которых движется по своей полосе движения wi и пересечет место перехода дороги через bi секунд. Пешеход НЕ может останавливаться между полосами дороги. Он может остановиться только у одного из краев дороги. Если же он находится на разграничителе полос, то он обязан переходить одну из соседних полос, то есть двигается вперед или назад. При этом, если он уже начал переходить полосу, то он не может остановиться и пересечение очередной полосы движения займет у него время t.

В начальный момент времени пешеход находится на краю дороги, ближайшая к которому полоса имеет номер 1. Дорога считается бесконечной в обе стороны. Пешеход может двигаться только по прямой, перпендикулярной дороге, то есть, он идет или ждет на одном из краев дороги, или идет прямо, или назад. Найдите минимальное время, за которое пешеход может перейти дорогу (пересечь все ее полосы движения) и не оказаться сбитым машиной. Пешеход считается сбитым машиной i, если момент времени bi он оказался на полосе wi. Но если он в это время находился между полосами или в начале и в конце пути, то машина его не задевает.

Формат входного файла

Во входном файле содержатся числа K,N,t, за которыми следует N пар чисел wi и bi

Формат выходного файла

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

Ограничения

0 ≤ N ≤ 2 * 105, 1 ≤ K,t ≤ 100, 0 ≤ bi ≤ 104, 1 ≤ wi ≤ K

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3 10
2 15
1 10
2 30
30

Задача Q. Охота на шушанчиков

Автор:А. Жуплев, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Чтобы наловить шушанчиков, Крокодил Гена отправляется в лес с чемоданом и ружьём, стреляющим усыпляющими дротиками. В лесу он становится в точку с координатами (XG; YG) и начинает внимательно смотреть по сторонам. Как только Гена видит шушанчика, он тут же стреляет в него, и скоро спящий шушанчик оказывается в чемодане Крокодила. Гена всегда стреляет мгновенно и точно.

Лес состоит из N деревьев. На плане i-ое дерево можно представить в виде круга с координатами центра (Xi; Yi) и радиусом Ri. Гена видит все точки с координатами (x, y), такие, что отрезок (x; y) − (XG; YG) не пересекает ни одно дерево.

Один шушанчик, гуляя по лесу, пришёл в точку с координатами (XS; YS). Услышав, что Крокодил Гена в лесу, он бросился бежать в нору с координатами (XH; YH). Требуется определить, сможет ли шушанчик добраться до норы так, чтобы Гена его не увидел.

Формат входного файла

Входной файл состоит из K тестов. В первой строке входного файла содержится число K. Далее следуют описания тестов.

Каждый тест описывается числами XS YS XH YH XG YG N, за которыми следуют N троек чисел Xi Yi Ri.

Формат выходного файла

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

Ограничения

1 ≤ K ≤ 10

 − 100 ≤ XS, YS, XH, YH, XG, YG, Xi, Yi≤ 100

1 ≤ Ri ≤ 100, 0 ≤ N ≤ 100

Деревья не пересекаются и не касаются. Позиции Гены, шушанчика и норы различаются и не находятся внутри деревьев.

Все числа во входном файле целые

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2

3 3 5 0 1 1
2
2 2 1
4 1 1

3 3 5 0 2 0
3
2 2 1
4 1 1
10 18 1
ESCAPE
CATCH

Задача R. Марсоход

Автор:И. Олейников, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:3 Мб
Выходной файл:output.txt  

Условие

В далеком будущем российские ученые собрали и отправили аппарат для исследования поверхности Марса — "Марсоход-1". Поверхность кратера, в который высадился марсоход, разбита на участки размером 1 x 1 метр каждый. Программа движения марсохода состоит из последовательности команд:

Координаты юго-западного угла кратера — (0, 0). Оси координат направлены с запада на восток и с юга на север.

Известно, что марсоход высадился где-то в прямоугольнике с координатами (x1, y1) − (x2, y2). К сожалению связь с марсоходом была потеряна по неизвестным причинам, но он успел передать, что полностью выполнил программу движения. Удалось также определить, что последний сигнал был послан из прямоугольника с координатами (x3, y3) − (x4, y4). Ученые хотят сократить зону поиска и просят вас написать программу, определяющую, на каких участках этого прямоугольника может находиться марсоход.

Формат входного файла

В первой строке входного файла содержатся целые числа x1 y1 x2 y2 x3 y3 x4 y4, во второй строке содержится программа марсохода.

Формат выходного файла

Выходной файл должен содержать abs(y4 − y3) + 1 строк по abs(x4 − x3) + 1 символов в каждой — изображение зоны поиска, на котором участки, где может находиться марсоход, отмечены символом 'x' (ASCII 120), а остальные — символом '.' (ASCII 46).

Ограничения

0 ≤ xi, yi ≤ 1000, количество команд в программе не превышает 30000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 2 2 3 3 4 4
ne
..
x.

Задача S. Пеленг НЛО

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Два радара, расположенные в точках с координатами (0, 0) и (100, 0), обнаружили неопознанный объект. По таинственной причине, связанной, возможно, с внеземной природой объекта, радары оказались способны определить только направление на объект (пеленг), но не расстояние до объекта. Пеленг измеряется в градусах, против часовой стрелки, начиная от направления "на восток" (т. е. пеленг второго радара относительно первого равен 0°, пеленг первого радара относительно второго — 180°).

Требуется найти координаты НЛО или определить, что это невозможно.

Формат входного файла

Во входном файле содержатся вещественные числа a и b, разделенные пробелами.

Формат выходного файла

В выходном файле должны содержаться два вещественных числа, x и y, представляющие координаты объекта с точностью до 4 знаков после запятой. Если определить координаты невозможно, следует вывести два числа 0 (нуль).

Ограничения

0 ≤ a, b ≤ 360

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
45.1 135.0
49.9127 50.0873
2
135.0 45.0
0 0

Задача T. Конденсация графа

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

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

Формат входного файла

Граф задан во входном файле следующим образом: первая строка содержит числа N и M. Каждая из следующих M строк содержат описание ребра - два целых числа из диапазона от 1 до N - номера начала и конца ребра.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 20000, 1 ≤ M ≤ 2000000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6 7
1 2
2 3
3 1
4 5
5 6
6 4
2 4
2
1 1 1 2 2 2

Задача U. КПК

Автор:И. Олейников, Т. Чистяков   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

Формат входного файла

Входной файл содержит числа N и M — соответственно число микросхем и проводов в КПК, за которыми следуют M пар чисел ai aj, означающие, что i-ая и j-ая микросхемы соединены проводом. Ток по проводу может течь в любом направлении.

Формат выходного файла

Выходной файл содержит сначала число K1 — количество проводов, которые нужно оставить в схеме, затем K1 пар чисел ai aj — описание проводов. После этого следует число K2 — число проводов, которые нужно добавить в схему, затем K2 пар чисел ai aj — описание проводов. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 3
1
2 3
1
1 2

Problem V. IP Networks

Author:NEERC 2005   Time limit:2 sec
Input file:ip.in   Memory limit:64 Mb
Output file:ip.out  

Statement

Alex is administrator of IP networks. His clients have a bunch of individual IP addresses and he decided to group all those IP addresses into the smallest possible IP network.

Each IP address is a 4-byte number that is written byte-by-byte in a decimal dot-separated notation "byte0.byte1.byte2.byte3" (quotes are added for clarity). Each byte is written as a decimal number from 0 to 255 (inclusive) without extra leading zeroes.

IP network is described by two 4-byte numbers - network address and network mask. Both network address and network mask are written in the same notation as IP addresses.

In order to understand the meaning of network address and network mask you have to consider their binary representation. Binary representation of IP address, network address, and network mask consists of 32 bits: 8 bits for byte0 (most significant to least significant), followed by 8 bits for byte1, followed by 8 bits for byte2, and followed by 8 bits for byte3.

IP network contains a range of 2n IP addresses where 0 ≤ n ≤ 32. Network mask always has 32 − n first bits set to one, and n last bits set to zero in its binary representation. Network address has arbitrary 32 − n first bits, and n last bits set to zero in its binary representation. IP network contains all IP addresses whose 32 − n first bits are equal to 32 − n first bits of network address with arbitrary n last bits. We say that one IP network is smaller than the other IP network if it contains fewer IP addresses.

For example, IP network with network address 194.85.160.176 and network mask 255.255.255.248 contains 8 IP addresses from 194.85.160.176 to 194.85.160.183 (inclusive).

Input file format

The first line of the input file contains a single integer number m. The following m lines contain IP addresses, one address on a line. Each IP address may appear more than once in the input file.

Output file format

Write to the output file two lines that describe the smallest possible IP network that contains all IP addresses from the input file. Write network address on the first line and network mask on the second. line.

Constraints

1 ≤ m ≤ 1000

Sample tests

No. Input file (ip.in) Output file (ip.out)
1
3
194.85.160.177
194.85.160.183
194.85.160.178
194.85.160.176
255.255.255.248

Задача W. 0 - a, 1 - ab

Автор:algolist   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Дана строка s, состоящая из N символов 0 или 1, а также строка t, состоящая из M символов a или b,

Над строкой s разрешено производить следующие действия:

Требуется определить, можно ли преобразовать строку s в строку t при помощи указанных действий.

Формат входного файла

Первая строка входного файла содержит числа N M.

Вторая строка входного файла содержит строку s.

Третья строка входного файла содержит строку t.

Формат выходного файла

Выходной файл должен содержать единственный символ Y или N.

Ограничения

1 ≤ N, M ≤ 10000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
101
bab
Y
2
4 3
1001
bab
N

Problem X. Heapsort

Author:Andrew Stankevich (original idea, text, solution)   Time limit:2 sec
Input file:heapsort.in   Memory limit:64 Mb
Output file:heapsort.out  

Statement

A well known algorithm called heapsort is a deterministic sorting algorithm taking O(n log n) time and O(1) additional memory. Let us describe ascending sorting of an array of different integer numbers.

The algorithm consists of two phases. In the first phase, called heapification, the array of integers to be sorted is converted to a heap. An array a[1…n] of integers is called a heap if for all 1 ≤ i ≤ n the following heap conditions are satisfied:

- if 2in then a[i] > a[2i];

- if 2i + 1 ≤ n then a[i] > a[2i + 1].

We can interpret an array as a binary tree, considering children of element a[i] to be a[2i] and a[2i + 1]. In this case the parent of a[i] is a[i div 2], where i div 2 = floor(i / 2). In terms of trees the property of being a heap means that for each node its value is greater than the values of its children.

In the second phase the heap is turned into a sorted array. Because of the heap condition the greatest element in the heapified array is a[1]. Let us exchange it with a[n], now the greatest element of the array is at its correct position in the sorted array. This is called extract-max.

Now let us consider the part of the array a[1 ... n-1]. It may be not a heap because the heap condition may fail for i=1. If it is so (that is, either a[2] or a[3], or both are greater than a[1]) let us exchange the greatest child of a[1] with it, restoring the heap condition for i=1. Now it is possible that the heap condition fails for the position that now contains the former value of a[1]. Apply the same procedure to it, exchanging it with its greatest child. Proceeding so we convert the whole array a[1 ... n-1] to a heap. This procedure is called sifting down. After converting the part a[1 ... n-1] to a heap by sifting, we apply extract-max again, putting second greatest element of the array to a[n-1], and so on.

For example, let us see how the heap a=(5, 4, 2, 1, 3) is converted to a sorted array. Let us make the first extract-max. After that the array turns to (3, 4, 2, 1, 5). Heap condition fails for a[1] = 3 because its child a[2] = 4 is greater than it. Let us sift it down, exchanging a[1] and a[2]. Now the array is (4, 3, 2, 1, 5). The heap condition is satisfied for all elements, so sifting is over. Let us make extract-max again. Now the array turns to (1, 3, 2, 4, 5). Again the heap condition fails for a[1]; exchanging it with its greatest child we get the array (3, 1, 2, 4, 5) which is the correct heap. So we make extract-max and get (2, 1, 3, 4, 5). This time the heap condition is satisfied for all elements, so we make extract-max, getting (1, 2, 3, 4, 5). The leading part of the array is a heap, and the last extract-max finally gives (1, 2, 3, 4, 5).

It is known that heapification can be done in O(n) time. Therefore, the most time consuming operation in heapsort algorithm is sifting, which takes O(n * log (n)) time.

In this problem you have to find a heapified array containing different numbers from 1 to n, such that when converting it to a sorted array, the total number of exchanges in all sifting operations is maximal possible. In the example above the number of exchanges is 1+1+0+0+0 = 2, which is not the maximum. (5, 4, 3, 2, 1) gives the maximal number of 4 exchanges for n=5.

Input file format

Input file contains n.

Output file format

Output the array containing n different integer numbers from 1 to n, such that it is a heap, and when converting it to a sorted array, the total number of exchanges in sifting operations is maximal possible. Separate numbers by spaces.

Constraints

1 ≤ n ≤ 50000

Sample tests

No. Input file (heapsort.in) Output file (heapsort.out)
1
6
6 5 3 2 4 1

Problem Y. Ford-Bellman

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3 1
1 2 5
1 3 10
2 3 2
0 5 7

Problem Z. Joseph's Problem

Author:NEERC 2005   Time limit:2 sec
Input file:joseph.in   Memory limit:64 Mb
Output file:joseph.out  

Statement

Joseph likes taking part in programming contests. His favorite problem is, of course, Joseph's problem. It is stated as follows. There are n persons numbered from 0 to n. 1 standing in a circle. The person number k, counting from the person number 0, is executed. After that the person number k of the remaining persons is executed, counting from the person after the last executed one. The process continues until only one person is left. This person is a survivor. The problem is, given n and k detect the survivor's number in the original circle. Of course, all of you know the way to solve this problem. The solution is very short, all you need is one cycle:

r := 0;
for i from 1 to n do
  r := (r + k) mod i;
return r;

Here "x mod y" is the remainder of the division of x by y But Joseph is not very smart. He learned the algorithm, but did not learn the reasoning behind it. Thus he has forgotten the details of the algorithm and remembers the solution just approximately. He told his friend Andrew about the problem, but claimed that the solution can be found using the following algorithm:

r := 0;
for i from 1 to n do
  r := r + (k mod i);
return r;

Of course, Andrew pointed out that Joseph was wrong. But calculating the function Joseph described is also very interesting. Given n and k, find ki = 1(k mod i).

Input file format

The input file contains n and k.

Output file format

Output the sum requested.

Constraints

1 ≤ n, k ≤ 109

Sample tests

No. Input file (joseph.in) Output file (joseph.out)
1
5 3
7

1.356s 0.015s 61