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

Автор:А. Кленин, Е. Иванова   Ограничение времени: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

Задача B. Комментарии-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

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

Автор:А. Кленин   Ограничение времени: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
.............
.......+---+.
.......|###|.
.......|###|.
.......|###|.
.......|###|.
.+---+.|###|.
.|###|.|###|.
-+---+-+---+-

Задача D. Форматирование таблицы

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

Условие

Вам предлагается отформатировать таблицу, данную во входном файле.

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

Первая строка входного файла содержит несколько букв l,c,r. Их количество равно количеству столбцов в таблице. Каждая буква задает расположение текста в соответствующем столбце ( l значит, что текст сдвинут до упора влево, с — что текст расположен по середине, r — что текст сдвинут вправо). Далее следуют не менее двух и не более 100 строк данных, каждая из которых задает соответствующую строку таблицы. Каждая строка содержит несколько записей, разделенных амперсантом ('&') Количество записей в каждой строке равно количеству столбцов. Каждая запись должна располагаться в соответствующем столбце. Первая строка данных задает заголовок таблицы, а остальные — тело таблицы. Знак '&' не содержится в ячейках таблицы.

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

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

Ограничения

  1. длина любой строки входного файла не превышает 250 символов
  2. в таблице не более 100 строк
  3. в таблице не более 100 столбцов

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

Входной файл (format.in) Выходной файл (format.out)
1
lr
EXPRESSION&RESULT
2+2&4
2+2*2&6
+------------+--------+
| EXPRESSION | RESULT |
+------------+--------+
| 2+2        |      4 |
| 2+2*2      |      6 |
+------------+--------+
2
lcr
LEFT&CENTER&RIGHT
1&2&3
the&the&the
longest&longest&longest
kitten&kitten&kitten
blitz&blitz&blitz
+---------+---------+---------+
| LEFT    | CENTER  |   RIGHT |
+---------+---------+---------+
| 1       |    2    |       3 |
| the     |   the   |     the |
| longest | longest | longest |
| kitten  | kitten  |  kitten |
| blitz   |  blitz  |   blitz |
+---------+---------+---------+

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

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

Условие

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
aA
Aa
aa
AA1
aA
Aa1
aa2
AA11

Problem F. C----

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

Statement

C---- language was designed specifically for students who failed standard course of Compiler Programming. C---- program is a list of statements. Each statement is one of:

Variable names are single small Latin letters. Constants are integers in range from 0 to 109. There are no spaces anywhere except after int and print keywords.

Each variable is declared at most once in the block, but variables with same name may be declared in different blocks. It that case, name refers to the variable declared in the nearest enclosing block. Note that variables may be defined in the middle of the block.

The program is guaranteed to be correct — all blocks are properly balanced, variables are referenced only after declaration, variables are always initialized before reading, etc. Program contains at least one print statement.

Your program must execute a given C---- program.

Input file format

First line of input file contains integer N. Following N lines contain one C---- statement each.

Output file format

Output file must contain a sequence of integers — one integer for each print statement.

Constraints

3 ≤ N ≤ 1000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
10
int a
int x
{
a=50
int a
a=60
x=a
print x
}
print a
60
50

Задача G. Косая спираль

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

Условие

Изображение косой спирали из N витков представляет собой 4 N строк по 4 N − 1 символу каждая.

Виток спирали с номером i состоит из четырёх отрезков, идущих вправо-вниз, влево-вниз, влево-вверх и вправо-вверх соответственно. Первые два отрезка состоят из 2 i − 1 символов каждый, последние два — из 2 i символов каждый.

Отрезки, направленные вправо-вниз и влево-вверх, изображаются символами '\' (ASCII 92). Отрезки, направленные влево-вниз и вправо-вверх, изображаются символами '/' (ASCII 47). Остальная часть изображения заполняется символами '.' (ASCII 46)

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

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

Задача H. Длинное взятие

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

Условие

На шашечной доске размером N × N клеток расположены несколько белых и несколько черных шашек. Горизонтали доски обозначены числами 1, 2, 3, … снизу вверх. (То есть первая строка входных данных описывает горизонталь доски с номером N, вторая N − 1 и т.д.) Вертикали обозначены буквами a, b, c, … слева направо. Клетка, таким образом, задается комбинацией из буквы и числа, например d12. Ход шашки задается перечислением всех клеток, которые она посетила за этот ход, включая начальную и конечную. Обозначения клеток при этом разделяются знаком - (минус). Например: a1-c3-e1.

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

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

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

В первой строке входного файла содержится число N. В следующих N строках — описание позиции, состоящее из символов '.' (точка), 'O' (заглавная латинская О),'X' (заглавная латинская X). Они определяют пустую клетку, белую шашку и черную шашку соответственно.

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

В выходном файле должна содержаться единственная строка вида L1 N1 − L2 N2 − … − LK NK, где K ≥ 1, или Impossible если взятие невозможно.

Ограничения

1 ≤ N ≤ 12

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
.....
.O.O.
....X
.O.O.
X....  
e3-c1-a3-c5-e3  
2
4
X...
....
....
...O  
Impossible

Problem I. H2O and other slogans

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

When young programmer Vasya was even younger, he found a book on organic chemistry. He did not understand a thing, but liked the pictures of structural chemical formulae in the book and started to draw many similar ones.

Years later, while clearing his room, Vasya found his old drawings and wondered which of them were correct. Since there were many of them, he decided to write a program for that task.

The structural formula of a chemical compound is a graphical representation of the molecular structure showing how the atoms are arranged. Atoms are denoted by letters, and chemical bonds between them — by line segments.

Formula is represented in input file as a two-dimensional array of characters. Each character may be: '.' (ASCII 46) — empty space, 'C' — carbon atom, 'H' — hydrogen atom, 'O' — oxygen atom, '|' (ASCII 124), '/' (ASCII 47), '\' (ASCII 92), '-' (ASCII 45) — chemical bonds. Bonds in correct formula are drawn as straight vertical, horizontal or diagonal lines without intersections. Atoms represented by adjacent letters are not considered bonded.

Correct formula must contain at least one atom and must be connected (there must be a path from each atom to each other passing through bonds).

Additionally, Vasya wants to check that the number of bonds for each atom is equal to the valency number of the corresponding chemical element. For simplicity, he decided that number would be always equal to 4 for carbon, 2 for oxygen and 1 for hydrogen.

Input file format

First line of input file contains integers N M. Following N lines contain M characters each — formula representation.

Output file format

Output file must contain a single string: GOOD, if the drawing represents correct formula, VALENCY if the formula is correct in everything except valencies, and BAD otherwise.

Constraints

1 ≤ N, M ≤ 50

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 3
-C|
..|
BAD
2
3 6
..HH..
./..\.
O----O
GOOD
3
3 6
H--C..
....\.
.....H
VALENCY

Задача J. Vasin Multimedia Player

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

Условие

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

Изучив некоторые аналогичные программы, Вася решил реализовать следующий алгоритм: когда пользователь выбирает файл для воспроизведения, то вместе с этим файлом добавляются также все "похожие" на него файлы в алфавитном порядке. Файлы добавляются даже в случае, если они уже есть в списке воспроизведения. Файлы считаются "похожими", если их имена имеют (непустое) одинаковое начало, после которого идёт символ разделителя либо конец строки. Разделителями считаются символы ' ' (пробел, ASCII 32), '_' (подчёркивание, ASCII 95) и '-' (минус, ASCII 45).

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

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

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

Выходной файл должен содержать итоговый список имён файлов (по одному в строке).

Ограничения

1 ≤ N ≤ 100; 0 ≤ M ≤ 100. Все имена файлов различны, состоят из маленьких латинских букв, цифр и разделителей и имеют длину от 1 до 100 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
11
five_-_dont_wanna_let_u_go
symphony 40 part 2 andante
ace of base_-_all_that_she_wants
queen - radio ga ga
symphony 40 part 1 allegro
ace of base_-_happy_nation
symphony
five and queen_-_we will rock you
symphony 40
ace of base_-_beautiful_life
queen - the_show_must_go_on
4
symphony 40
queen - radio ga ga
five and queen_-_we will rock you
symphony 40 part 1 allegro
symphony
symphony 40
symphony 40 part 1 allegro
symphony 40 part 2 andante
queen - radio ga ga
queen - the_show_must_go_on
five and queen_-_we will rock you
five_-_dont_wanna_let_u_go
symphony
symphony 40
symphony 40 part 1 allegro
symphony 40 part 2 andante

0.821s 0.026s 33