Задача A. Сложение неотрицательных длинных чисел

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

Условие

Требуется по данным целым неотрицательным числам a и b вычислить значение a + b.

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

В первой строке число a. Во второй строке число b.

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

Единственное число, равное a + b.

Ограничения

0 ≤ a, b ≤ 1010000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5
8
2
100000000000000000000
29
100000000000000000029

Задача B. Сложение N чисел

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

Условие

Дана последовательность целых чисел A1, …, AN. Вычислить их сумму.

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

Во входном файле содержатся числа A1… AN.

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

В выходном файле должно содержаться единственное число — сумма всех чисел входного файла.

Ограничения

0 ≤ Ai ≤ 10000, 1 ≤ N ≤ 1000.

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

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

Задача C. Города

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

Условие

Юный программист решил придумать собственную игру. Игра происходит на поле размером N×N клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.

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

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

Требуется написать программу, которая с учетом сказанного разделит клетки заданного игрового поля между двумя государствами.

Система оценивания

Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.

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

Первая строка входного файла содержит одно целое положительное число N, задающее размер игрового поля. Последующие N строк содержат по N заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: 'C' обозначает клетку, занятую городом, 'D' — пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их четное число.

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

Выходной файл должен содержать N строк по N цифр (без пробелов) в каждой, кодирующих соответствующие клетки. Цифра 1 обозначает, что данная клетка принадлежит первому государству, цифра 2 — данная клетка принадлежит второму государству. Если решений несколько, необходимо вывести любое из них.

Ограничения

1 ≤ N ≤ 50

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

Входной файл (cities.in) Выходной файл (cities.out)
1
3
DDD
DDC
DDC
111
111
112
2
5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD
11111
11111
12222
22222
22222

Задача D. Комбинированная эстафета

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

Условие

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

Тренер эстафетной команды знает время в секундах, за которое каждый из членов команды преодолевает дистанцию каждым из стилей.

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

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

Входной файл состоит из четырёх строк по четыре числа в каждой. j-ое число в i-ой строке (обозначим его tij) означает время, за которое i-ый спортсмен проходит дистанцию j-ым стилем. Каждое из чисел tij задано не более чем с двумя знаками после десятичной точки.

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

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

Ограничения

0 ≤ tij ≤ 120

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

Входной файл (input.txt) Выходной файл (output.txt)
1
49.61 55.47 61.97 53.33
53    59.5  66.5  57.5
56    63    70    61
59.5  67.5  75    65
3 2 4 1 

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

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

Условие

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

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

Промежуток между столбцами, а также поля слева, справа и сверху гистограммы должны составлять один символ. В основании (нижней строке) гистограммы промежутки и поля должны изображаться символом '-' (ASCII 45), все остальные промежутки и поля — символом '.' (ASCII 46).

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

Входной файл содержит число N, за которым следуют числа a1, a2, …, aN.

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

Выходной файл должен содержать max(ai) + 3 строк длиной 6 N + 1 символов каждая — изображение гистограммы.

Ограничения

1 ≤ N ≤ 100, 1 ≤ ai ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 6
.............
.......+---+.
.......|###|.
.......|###|.
.......|###|.
.......|###|.
.+---+.|###|.
.|###|.|###|.
-+---+-+---+-

Задача F. Библиотекарь

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

Условие

Аполлинарий Матвеевич — старый, седой библиотекарь. Сегодня он в очень хорошем настроении, потому что библиотеке подарили компьютер.

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

Однажды в библиотеку зашёл читатель. Он дал Аполлинарию Матвеевичу список тем и попросил его подобрать книги по этим темам. Аполлинарий Матвеевич обрадовался: у него есть база данных! Но стоп: как найти в базе данных нужную информацию? Для этого нужна программа.

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

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

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

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

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

Далее входной файл содержит целое число M — количество тем в списке, подготовленном читателем. Далее следует список тем.

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

Для каждой темы требуется вывести строку "Topic: название темы". Далее должна следовать строка "Subject: название области знаний". Далее должна следовать строка "Books:" (без пробелов). Далее должен следовать список книг в том порядке, в котором они перечислены во входном файле.

Ограничения

1 ≤ N ≤ 50

1 ≤ M ≤ 10

Количество книг, относящихся к определённой области знаний, от 1 до 100.

Количество тем, затронутых в определённой книге, от 1 до 10.

Все названия во входном файле имеют длину от 1 до 50 символов и состоят из маленьких латинских букв.

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
mathematics
2
algebra
3
lines
equations
coordinates
geometry
3
triangles
coordinates
lines
physics
2
mechanics
3
force
velocity
mass
gravitation
2
force
mass
5
force
triangles
velocity
coordinates
mass
Topic: force
Subject: physics
Books:
mechanics
gravitation
Topic: triangles
Subject: mathematics
Books:
geometry
Topic: velocity
Subject: physics
Books:
mechanics
Topic: coordinates
Subject: mathematics
Books:
algebra
geometry
Topic: mass
Subject: physics
Books:
mechanics
gravitation

Задача G. Океанариум

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

Условие

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

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

Например, если в первый раз Петя увидел трёх гуппи и одного вуалехвоста, а во второй раз — четырёх вуалехвостов, то всего в аквариуме не менее 7 рыбок.

Рекомендуется рассмотреть частичные решения

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

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

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

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

Ограничения

1 ≤ N, Ki ≤ 50, длина названий не превосходит 255 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
2
Carassius auratus
Poecilia reticulata
2
2
3
5
Lionhead
Pompom
Pearlscale
Pearlscale
Lionhead
2
Pompom
Pompom
5
Lionhead
Lionhead
Ryukin
Pearlscale
Lionhead
8

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

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

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

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

Входной файл содержит последовательность чисел.

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

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 106, сами числа — в диапазоне от 231 до 231 − 1.

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

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

Задача I. Форматирование текста

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

Условие

Многие системы форматирования текста, например TEX или Wiki, используют для разбиения текста на абзацы пустые строки. Текст представляет собой последовательность слов, разделенных пробелами, символами перевода строк и следующими знаками препинания: «,», «.», «?», «!», «-», «:» и «'» (ASCII коды 44, 46, 63, 33, 45, 58, 39). Каждое слово в тексте состоит из заглавных и прописных букв латинского алфавита и цифр. Текст может состоять из нескольких абзацев. В этом случае соседние абзацы разделяются одной или несколькими пустыми строками. Перед первым абзацем и после последнего абзаца также могут идти одна или несколько пустых строк.

Дальнейшее использование исходного текста предполагает его форматирование, которое осуществляется следующим образом. Каждый абзац должен быть разбит на строки, каждая из которых имеет длину не больше W. Первая строка каждого абзаца должна начинаться с отступа, состоящего из B пробелов. Слова внутри одной строки должны быть разделены ровно одним пробелом. Если после слова идет один или несколько знаков препинания, они должны следовать сразу после слова без дополнительных пробелов. Если очередное слово вместе со следующими за ним знаками препинания помещается на текущую строку, оно размещается на текущей строке. В противном случае, с этого слова начинается новая строка. В отформатированном тексте абзацы не должны разделяться пустыми строками. В конце строк не должно быть пробелов.

Требуется написать программу, которая по заданным числам W и B и заданному тексту выводит текст, отформатированный описанным выше образом.

Система оценивания

Правильные решения для тестов, в которых заданный текст состоит из одного абзаца и входной файл не содержит пустых строк, будут оцениваться из 30 баллов.

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

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

Первая строка входного файла содержит два целых числа: W и B

Затем следует одна или более строк, содержащих заданный текст.

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

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

Ограничения

5 ≤ W ≤ 100

1 ≤ B ≤ 8

B < W

Длина слова в тексте вместе со следующими за ними знаками препинания не превышает W, а длина первого слова любого абзаца вместе со следующими за ним знаками препинания не превышает (W − B).

Размер входного файла не превышает 100 Кбайт. Длина каждой строки во входном файле не превышает 250.

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

Входной файл (format.in) Выходной файл (format.out)
1
20 4
Yesterday, 
All my troubles seemed so far away, 
Now it looks as though they're here to stay, 
Oh, I believe in yesterday. 

Suddenly, 
I'm not half the man I used to be, 
There's a shadow hanging over me, 
Oh, yesterday  came suddenly...
    Yesterday, All
my troubles seemed
so far away, Now it
looks as though
they' re here to
stay, Oh, I believe
in yesterday.
    Suddenly, I' m
not half the man I
used to be, There' s
a shadow hanging
over me, Oh,
yesterday came
suddenly...

Задача J. Комментарии-2: Вложенные комментарии

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

Условие

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

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

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

Входной файл содержит не более 1000 строк длиной не более 256 символов каждая.

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abc/*de/*f*/*/x
abcx
2
ab/*fg/*
c*/qw
/*rt
ab/*fgqw
/*rt

Задача K. Комментарии

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

Условие

Джон, хотя и пишет на языке С, дает файлам расширение CPP, чтобы использовать в своих программах комментарии в С++-стиле (от // до конца строки). Обычный С-комментарий, который начинается с символов "/*" и заканчивается символами "*/", Джон также иногда использует, обычно для многострочных комментариев. Для участия в конкурсе программ необходимо, чтобы программа соответствовала стандартам языка ANSI С, и Джону нужно заменить все C++-комментарии на стандартные. Для этого в C++-комментарии можно заменить "//" на "/*" и добавить "*/" в конце строки. Иногда в C++-комментарии может встретиться последовательность символов "*/", в этом случае нужно вставить пробел между двумя этими символами: "* /". К счастью внутри строковых констант в программе Джона не встречаются последовательностей "//", "/*" и "*/".

Напишите программу, которая преобразует в программе Джона C++-комментарии в C-комментарии.

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

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

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

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

Ограничения

Файл состоит из не более 100 строк длиной не более 100 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
#include &lt;stdio.h&gt;
/* Пример программы
 */
int main() 
{ printf( //Печать
      "Hello, world");
  return 0; //*/*
}
#include &lt;stdio.h&gt;
/* Пример программы
 */
int main() 
{ printf( /*Печать*/
      "Hello, world");
  return 0; /** /**/
}

Problem L. Python terrarium

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

Statement

A zoology research lab has a terrarium with rare species of snakes. Terrarium is a flat box filled with soil, and has a glass top allowing to watch the snakes. There are trenches in the soil, and snakes constantly move along the trenches. All snakes have diameter of 1 cm and integer length of no less than 2 cm.

While watching the snakes, the zoologists discovered a pattern in their movement: each snake moves at a speed of 1 cm per second forward, until it encounters either a wall or another snake. Faced an obstacle, snake first tries to turn right, if there is also obstacle on the right, then it tries to turn left. If there is obstacle on the left also, the snake waits for a second before trying to move again.

In order to validate the discovery, it was decided to write a program that simulates snakes' behaviour. This task was assigned to you.

The terrarium is represented by an array of N × N characters. Each character is one of:

Snakes are represented by latin letters, so there are no more than 26 snakes in terrarium. Snakes try to move in alphabetical order every second.

Your program must output the state of the terrarium after T seconds.

Input file format

First line of input file contains integers N T. Following N lines contain N characters each — the initial state of the terrarium. The input file guarantees unambiguous recognition of snakes — all snakes are continuous, every character of snake's body has exactly two neighbour characters belonging to the same snake, while head and tip of the tail have exactly one.

Output file format

Output file must contain N lines of N characters — the state of the terrarium after T seconds.

Constraints

2 ≤ N ≤ 1000, 1 ≤ T ≤ 106.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 8
.bB.
....
a.#.
aaA.
.baa
.BAa
..#.
....
2
7 100000
aA.....
a#####D
aa....d
......d
......d
......d
.......
aaaaADd
.#####d
......d
......d
.......
.......
.......

Задача M. Правильная запись номера

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

Условие

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

Российский телефонный номер в международном формате выглядит следующим образом: +7␣код_региона␣локальный_номер. В зависимости от длины кода региона существует 4 допустимых варианта записи:

+7, код региона и локальный номер отделяются друг от друга пробелом (ASCII 32), цифры внутри локального номера делятся на группы символом "тире" (ASCII 45) только так, как описано выше, другие варианты, например, 1-23-45-67 и т. д. недопустимы.

Сотрудник отдела кадров НИИ АСМ просит Вас написать программу, конвертирующую телефонный номер в международный формат.

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

Входной файл содержит единственную строчку с телефонным номером.

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

Выходной файл должен содержать единственную строчку — телефонный номер в международном формате.

Ограничения

Каждый телефонный номер работника начинается с подстроки +7 после которой следует код региона и локальный номер. Код региона — первый блок подряд идущих цифр после +7. В качестве символов разделителя могут быть использованы пробелы (ASCII 32) и тире (ASCII 45). Код региона может быть также обрамлён круглыми скобками (ASСII 40 и ASСII 41), в этом случае символы разделителя вокруг скобок могут быть опущены.

Суммарное количество цифр в коде региона и локальном номере равно 10. Длина входной строки не превышает 25 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
+7 (123)456-7-890
+7 123 456-78-90
2
+7(9876)543 210
+7 9876 54-32-10
3
+7-31415 92 - 65-3
+7 31415 9-26-53

Problem N. Count Squares

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

Statement

Given a set of points with integer coordinates xi, yi, i = 1… N, your program must find all the squares having each of four vertices in one of these points.

Input file format

Input file contains integer N followed by N pairs of integers xi yi.

Output file format

Output file must contain a single integer — number of squares found.

Constraints

104 ≤ xi, yi ≤ 104, 1 ≤ N ≤ 2000. All points in the input are different.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 0 0 4 3 -3 4 1 7
1
2
9
1 1  1 2  1 3  
2 1  2 2  2 3  
3 1  3 2  3 3
6

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

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

Условие

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

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

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

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

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7.2
102.
47
84.1
102.84.17.247
2
.0.
00
1
2.0
100.0.2.0
2.0.0.100


Задача P. Перепутанные диски

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

Условие

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

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

Например, пусть у Васи есть три компакт-диска с играми — "Цивилизация", "Тетрис" и "Сапер". Пусть Вася сначала начал играть в "Цивилизацию", а затем решил поиграть в "Тетрис". Тогда после этого диск с "Цивилизацией" окажется в коробке от "Тетриса". Пусть затем он решил поиграть в "Сапера". Тогда диск от "Тетриса" окажется в коробке от "Сапера". Если после этого он снова решит поиграть в "Цивилизацию" (заметим, что для этого он достанет ее из коробки от "Тетриса"), то игра "Сапер" окажется в коробке от "Тетриса", а "Цивилизация" — в CD-приводе Васиного компьютера.

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

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

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

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

Выведите в выходной файл k строк, где k — количество различных игр, в которые играл Вася. Каждая строка должна иметь вид "game - box", где game — название игры, а box - название игры, в коробке от которой лежит игра game. Если соответствующая игра лежит в CD-приводе компьютера, вместо box выведите "*" (звездочку). Выводите игры в произвольном порядке.

Ограничения

1 ≤ n ≤ 1000, длина названия не превышает 50 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
Civilization
Tetris
Minesweeper
Civilization
Civilization - *
Tetris - Minesweeper
Minesweeper - Tetris

Задача Q. Код Хаффмана

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

Условие

Построить код Хаффмана для алфавита из N символов и соответствующих им частот встречаемости.

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

Во входном файле содержится число N, за которым следуют N чисел fi — частота встречаемости i−го символа.

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

Выходной файл должен содержать N строк вида hi — коды Хаффмана для символов в порядке, соответствующем входному файлу. Каждый код должен представлять собой строку из цифр 0 и 1. Если существует несколько решений, вывести любое из них.

Ограничения

2 ≤ N ≤ 100, 0 ≤ fi ≤ 100000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6
45
13
12
16
9
5
0
101
100
111
1101
1100

Задача R. Определить век по году

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

Условие

Когда Андрей учился в начальной школе, его учили определять, к какому веку относится заданный год. Теперь Андрей хорошо знает, что, например, 2001 год относится к XXI веку, а 2000 год — к XX веку.

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

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

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

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

Входной файл содержит целое число Y — номер года.

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

Требуется вывести в выходной файл номер века, к которому относится год Y, в римской системе счисления, используя заглавные буквы латинского алфавита I, V, X.

Ограничения

1 ≤ Y ≤ 3000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2001
XXI
2
2000
XX
3
658
VII
4
2703
XXVIII

Задача S. Девушки-программисты

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

Условие

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

Перед чемпионатом производится формирование команд: участники выбирают, с кем они будут в одной команде.

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

У жюри есть мешок с N шариками. На шариках написаны числа от 1 до N.

Всего участников N (причём N кратно трём), среди них M девушек.

Жюри достаёт из мешка 3 шарика (считаем, что все возможные тройки шариков равновероятны). Участники с соответствующими номерами в списке объединяются в команду.

Итак, требуется для каждого k = 0, 1, 2, 3 вычислить вероятность pk случайного события, состоящего в том, что в этой команде будет k девушек.

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

Входной файл содержит два целых числа: N M.

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

Требуется вывести в выходной файл 4 вещественных числа: p0, p1, p2, p3 — с точностью до 5 знаков после десятичной точки.

Ограничения

1 ≤ M ≤ N ≤ 100.

N делится на 3.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
0.00000 1.00000 0.00000 0.00000
2
3 2
0.00000 0.00000 1.00000 0.00000
3
6 4
0.00000 0.20000 0.60000 0.20000
4
6 2
0.20000 0.60000 0.20000 0.00000

Задача T. rrrrr...

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

Условие

Определим функцию r(p, q), где p и q — строки символов, следующим образом: функция удаляет первый символ из строки p, и присоединяет к концу получившейся строки первый символ строки q. Например, r('abc', 'def') = 'bcd'.

Исходя из данной строки x можно сгенерировать различные выражения, например r(x,x), r(r(x,r(x,x)),x) и т.п. Требуется сгенерировать выражение, значение которого равно строке y, либо определить, что это невозможно.

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

Входной файл содержит строки x и y.

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

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

Ограничения

Строки во входном файле состоят из строчных латинских букв, длина строк не превосходит 100 символов. Длина выражения не должна превосходить 100000 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
ab
ba
r(x,x)
2
ab
xy
NO

0.303s 0.006s 51