Задача A. Правдивая летопись ≡

Условие

"...И узрели они войско вражье хазарское. И было хазарам несметное число." — Тут летописец задумался. Он знал, что число воинов было равно N. Однако, это число могло делиться на три, а могло (что еще хуже) содержать цифру три в десятичной записи! Число три счастливое, а это никак не согласуется с образом врага!

Поэтому летописец решил написать вместо числа N другое число M, которое не делится на три и не содержит в десятичной записи цифру три. Разумеется, число M не может быть меньше N (летописец не преуменьшает количество воинов). С другой стороны, число M должно как можно меньше отличаться по величине от N, иначе летописца могут обвинить в некомпетентности. Помогите летописцу найти нужное M.

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

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

Ограничения

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

1

1

3

4

12

14

Задача B. Скорость воробьёв ≡

Условие

Юный орнитолог Вася решил узнать, насколько быстро способны летать воробьи. Для этого он нашёл ряд из N кустов, растущих вдоль одно прямой на расстоянии ровно 1 метр друг от друга.

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

Однако оказалось, что на первой фотографии на каждом из кустов сидит ровно по одному воробью, а на второй — на i-м кусте сидят a_i воробьёв. (a₁ + a₂ + … + a_N = N).

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

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

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

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

В выходном файле должно содержаться единственное целое число — минимальная скорость воробья в м/с.

Ограничения

1 ≤ N ≤ 1000

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

3
1 1 1

0

5
0 2 3 0 0

2

Задача C. Гистограмма ≡

Условие

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

По данным целым числам a₁, a₂, …, a_N требуется построить гистограмму. Гистограмма должна состоять из N столбцов, i-й столбец должен изображаться прямоугольником высотой a_i и шириной в 3 символа. Столбцы должны быть:

• заполнены символом '#' (ASCII 35),
• ограничены сверху и снизу символами '-' (ASCII 45),
• ограничены слева и справа символами '|' (ASCII 124),
• ограничены по углам символами '+' (ASCII 43).

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

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

Ограничения

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

2
1 6

.............
.......+---+.
.......|###|.
.......|###|.
.......|###|.
.......|###|.
.+---+.|###|.
.|###|.|###|.
-+---+-+---+-

Задача D. Сбалансированное дерево ≡

Условие

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

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

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

Ограничения

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

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Problem E. Sudoku Checker ≡

Statement

The puzzle game of Sudoku is played on a board of N² × N² cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N².

The sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct position, fill all empty cells so that the final position is still correct.

This game is fairly popular in the Internet, and there are many sites which allow visitors to solve puzzles online. Such sites always have a subroutine to determine a correctness of a given position.

You are to write such a routine.

Input file format

Output file format

Constraints

Sample tests

2
0 0 0 0
0 0 0 0
0 0 2 0
0 0 0 1

CORRECT

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

INCORRECT

Задача F. Имена файлов ≡

Условие

I wish we had some way to handle it sanely, but I don't think a sane solution to case-insensitivity exists.

Linus Torvalds

На компьютере под управлением операционной системы Linux имеется каталог, содержащий N файлов. Пользователю требуется скопировать эти файлы на компьютер, работающий под управлением ОС Windows. К сожалению, файловая система Windows имеет странное свойство. Несмотря на то, что она сохраняет большие и малые буквы в именах файлов, имена, отличающиеся только регистром букв, считаются одинаковыми. Например, файлы с именами ChangeLog, CHANGELOG и changelog при копировании на файловую систему Windows попадут в один и тот же файл.

Чтобы избежать потери данных, предлагается при копировании переименовывать файлы по следующим правилам:

1. Файлы копируются в порядке перечисления в исходном каталоге.
2. Имена файлов считаются одинаковыми, если они совпадают с точностью до регистра.
3. Если при копировании очередного файла выяснилось, что файл с таким именем уже был скопирован, то к имени текущего файла добавляется суффикс "1".
4. Если имя, полученное после присоединения суффикса, также уже встречалось, то перебираются суффиксы "2", "3", ..., "10", "11", ... до тех пор, пока не найдётся суффикс, дающий уникальное имя.

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

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

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

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

Ограничения

1 ≤ N ≤ 10000, 1 ≤ M ≤ 255

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

4
aA
Aa
aa
AA1

aA
Aa1
aa2
AA11

Задача G. Поврежденный XML ≡

Условие

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки < (ASCII 60), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка > (ASCII 62). Примеры открывающих тегов: <a>, <dog>.

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш / (ASCII 47), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: </a>, </dog>.

XML-строка называется корректной, если она может быть получена по следующим правилам:

• Пустая строка является корректной XML-строкой.
• Если A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
• Если A — корректная XML-строка, то строка <X>A</X>, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.

Например, представленные ниже строки:

• <a></a>
• <a><ab></ab><c></c></a>
• <a></a><a></a><a></a>

• <a></b>
• <a><b>
• <a><b></a></b>

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.

Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

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

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

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

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

Ограничения

Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы <, > и /.

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

<a></b>

<b></b>

<a><aa>

<a></a>

<a><>a>

<a></a>

<a/</a>

<a></a>

Задача H. Восстановить IP ≡

Условие

Корректная запись IP-адреса — это строка, состоящая из четырёх десятичных чисел в диапазоне от 0 до 255 каждое, разделённых символом "точка" (ASCII 46). Компоненты записи IP-адреса не должны содержать лидирующих нулей.

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

Помогите Пете восстановить IP-адрес.

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

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

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

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

7.2
102.
47
84.1

102.84.17.247

.0.
00
1
2.0

100.0.2.0
2.0.0.100