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

Условие

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

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

Ограничения

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

3
5

8

100000000000000000000
29

100000000000000000029

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

Условие

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

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

Ограничения

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

1 2 3

6

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 50

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

3
DDD
DDC
DDC

111
111
112

5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD

11111
11111
12222
22222
22222

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

Условие

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

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

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

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

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

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

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

Ограничения

0 ≤ t_ij ≤ 120

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

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. Гистограмма ≡

Условие

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

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

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

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

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

Ограничения

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

2
1 6

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

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

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 50

1 ≤ M ≤ 10

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

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

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

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

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

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. Океанариум ≡

Условие

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

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

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

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

• N = 1,
• каждый листок содержит ровно одно название рыбки.

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

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

Ограничения

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

1
2
Carassius auratus
Poecilia reticulata

2

3
5
Lionhead
Pompom
Pearlscale
Pearlscale
Lionhead
2
Pompom
Pompom
5
Lionhead
Lionhead
Ryukin
Pearlscale
Lionhead

8

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

Условие

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

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

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

Ограничения

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

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

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

Условие

Многие системы форматирования текста, например 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.

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

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: Вложенные комментарии ≡

Условие

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

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

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

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

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

abc/*de/*f*/*/x

abcx

ab/*fg/*
c*/qw
/*rt

ab/*fgqw
/*rt

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

Условие

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

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

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

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

Ограничения

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

#include <stdio.h>
/* Пример программы
 */
int main() 
{ printf( //Печать
      "Hello, world");
  return 0; //*/*
}

#include <stdio.h>
/* Пример программы
 */
int main() 
{ printf( /*Печать*/
      "Hello, world");
  return 0; /** /**/
}

Problem L. Python terrarium ≡

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:

• '.' (ASCII 46) — trench
• '#' (ASCII 35) — wall
• 'A' to 'Z' — snake's head
• 'a' to 'z' — snake's body or tip of the tail

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

Input file format

Output file format

Constraints

Sample tests

4 8
.bB.
....
a.#.
aaA.

.baa
.BAa
..#.
....

7 100000
aA.....
a#####D
aa....d
......d
......d
......d
.......

aaaaADd
.#####d
......d
......d
.......
.......
.......

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

Условие

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

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

• +7␣123␣123-45-67
• +7␣1234␣12-34-56
• +7␣12345␣1-23-45
• +7␣123456␣12-34

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

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

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

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

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

Ограничения

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

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

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

+7 (123)456-7-890

+7 123 456-78-90

+7(9876)543 210

+7 9876 54-32-10

+7-31415 92 - 65-3

+7 31415 9-26-53

Problem N. Count Squares ≡

Statement

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

Input file format

Output file format

Constraints

Sample tests

4 0 0 4 3 -3 4 1 7

1

9
1 1  1 2  1 3  
2 1  2 2  2 3  
3 1  3 2  3 3

6

Задача O. Восстановить 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

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

Условие

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

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

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

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

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

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

Ограничения

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

4
Civilization
Tetris
Minesweeper
Civilization

Civilization - *
Tetris - Minesweeper
Minesweeper - Tetris

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

Условие

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

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

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

Ограничения

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

6
45
13
12
16
9
5

0
101
100
111
1101
1100

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ Y ≤ 3000.

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

2001

XXI

2000

XX

658

VII

2703

XXVIII

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

Условие

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

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

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

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

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

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

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

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

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

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

Требуется вывести в выходной файл 4 вещественных числа: p₀, p₁, p₂, p₃ — с точностью до 5 знаков после десятичной точки.

Ограничения

1 ≤ M ≤ N ≤ 100.

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

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

3 1

0.00000 1.00000 0.00000 0.00000

3 2

0.00000 0.00000 1.00000 0.00000

6 4

0.00000 0.20000 0.60000 0.20000

6 2

0.20000 0.60000 0.20000 0.00000

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

Условие

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

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

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

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

Ограничения

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

ab
ba

r(x,x)

ab
xy

NO