Задача A. Лабиринт ≡

Условие

Лабиринт задан как двумерный массив символов '.' и '#', означающих пустое пространство и стену соответственно. В любой не занятой стеной клетке может находиться Искатель. Ему разрешено перемещаться по клеткам лабиринта в четырех направлениях: вверх, вниз, влево и вправо. Покидать лабиринт через внешнюю границу запрещено, ибо за его пределами находится сплошная стена. Требуется написать программу, которая по заданному лабиринту определяет существует ли путь от входа к выходу.

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

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

Ограничения

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

3 3
S#.
.#F
...

YES

3 3
S#.
.#F
#..

NO

Problem B. Tetris alphabet ≡

Statement

The game of Tetris is played with four-connected blocks falling down the well having N rows and 20 columns. Each figure is marked with a unique English letter from 'A' to 'Z'.

Your program must, given the state of the well, determine the order in which the blocks fell down.

Input file format

Output file format

Constraints

Sample tests

6
...........XX.......
..........MMMM......
..........K.........
........KKK.........
.....ZAAA.FFF.......
.....ZZZA..F.B......

BFZAKMX

Problem C. Harder Sokoban Problem ≡

Statement

The game of sokoban is played in a rectangular labirinth of N by N cells with each cell either empty, denoted by '.' character (ASCII 46), or occupied by wall, denoted by '#' character (ASCII 35). There is also a single destination cell, denoted by '*' character (ASCII 42).

One player and one container are located in the empty cells of the labirinth. The player can move between the empty cells in horizontal or vertical direction. If the cell where the player tries to move is occupied by container, the container is "pushed" to the next cell in the same direction. That next cell must, of course, be empty.

The objective of the game is well-known: to place the container in the destination cell with the minimum number of moves. Your task, however, is different: given the field, select starting position for the player and the container so as to maximize the required number of moves.

Input file format

Output file format

Constraints

Sample tests

2
..
.*

0

3
..#
...
..*

10

Задача D. Квадратное озеро ≡

Условие

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

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

Ограничения

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

7 2
.......
...@...
.......
..@....
.......
.......
....@..

10

Задача E. Дробь в LATeX-е ≡

Условие

Издательская система LATeX предназначена для верстки сложных научно-технических текстов с большим количеством формул. Исходный файл для системы LATEX пишется на языке TEX и представляет собой текст документа, в который включены специальные символы и команды. Специальные символы и команды описывают размещение текста, в частности в математических формулах. Команда представляет собой последовательность латинских букв (регистр важен), перед которой стоит символ "\". Так, команда \frac предназначена для описания дроби, в которой числитель расположен над знаменателем. Рассмотрим простейшую структуру команды \frac.

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

Дадим также формальное определение выражения для нашей задачи:

• <выражение> ::= <элемент> | <элемент> <выражение>
• <элемент> ::= <дробь> | "{" <выражение> "}" | <другой математический элемент>
• <дробь> ::= "\frac" <тело дроби>
• <тело дроби> ::= <числитель><знаменатель>
• <числитель> ::= <пробелы><непробельный символ> | [<пробелы>] "{" <выражение> "}"
• <знаменатель> ::= <непробельный символ> | [<пробелы>] "{" <выражение> "}"
• <другой математический элемент> ::= произвольная последовательность печатных символов, не содержащая фигурных скобок и подстроки "\frac"
• <пробелы> ::= " " | " " <пробелы>
• <непробельный символ> ::= произвольный печатный символ, за исключением " ", "\", "{" и "}"

\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}

Чтобы в печатаемом документе вывести формулу, необходимо вычислить ее высоту для используемого при печати шрифта. Шрифт определяет размеры S - высоту отдельного символа и D - высоту горизонтальной дробной черты. Значения S и D задаются целыми числами. Ваша задача - для заданного выражения на языке TEX вычислить высоту формулы.

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

\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}

\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}

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

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

Ограничения

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

10 2
\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}

34

10 2
no fractions here

10

10 2
\frac        {\alpha}          {\beta+\sin{2+x}}

22

10 2
\cos{\frac{\alpha}b}

22

10 2
\frac a  {sin{a}}

22

10 2
\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}

46

10 2
\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}

46

Задача F. Ближайшее число - 1 ≡

Условие

Дан массив A, состоящий из N неотрицательных целых чисел.

Назовём правым (левым) соседом нулевого элемента ближайший к нему справа (слева) ненулевой элемент.

Требуется построить массив B, который получается из массива A заменой каждого нулевого элемента на его ближайшего соседа в массиве A. Если оба соседа отсутствуют либо расстояния до них равны, замена не производится (элемент остаётся нулевым).

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

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

Ограничения

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

5
0 0 1 0 2

1 1 1 0 2

4
8 0 0 6

8 8 6 6

Задача G. Форум ≡

Условие

Клуб Юных Хакеров организовал на своем сайте форум. Форум имеет следующую структуру: каждое сообщение либо начинает новую тему, либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме.

После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос — какая тема на их форуме наиболее популярна. Помогите им выяснить это.

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

Первая строка входного файла содержит целое число N — количество сообщений в форуме. Следующие строки содержат описание сообщений в хронологическом порядке.

Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения.

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

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

Ограничения

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

7
0
Олимпиада по информатике
Скоро третья командная олимпиада?
0
Новая компьютерная игра
Вышла новая крутая игра!
1
Она пройдет 24 ноября
1
В Санкт-Петербурге и Барнауле
2
Где найти?
4
Примет участие более 50 команд
6
Интересно, какие будут задачи

Олимпиада по информатике

Задача H. Бюрократия ≡

Условие

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

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

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

Ограничения

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

4 3
1 2
1 3
3 4

1 3 2 4

Problem I. Radio Coverage ≡

Statement

Radio station 'ACM Rock' is broadcasting over the circular area with center in point (x₀, y₀) and radius R. In order to increase the auditorium, it were suggested to build several relay stations. N locations were selected as candidate sites for relay stations. Relay station placed in i-th location will cover a circular area with center in point (x_i, y_i) and radius r_i, where center lies inside the area covered by the base station, (x₀ - x_i)² + (y₀ - y_i)² ≤ R².

Your task is to select a subset of sites for relay stations so that:

1. the covered areas for relays do not intersect (but may touch) one another,
2. the total area covered by base station and all relays is maximum possible.

Input file format

Output file format

Constraints

Sample tests

1 0 0 10
10 0 10

505.4816

Задача S. Обход доски конем ≡

Условие

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

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

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

Ограничения

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

1 1

A1

1 2

No solution

3 4

A1 B3 C1 A2 B4 C2 A3 B1 C3 A4 B2 C4

Задача T. Выражение ≡

Условие

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

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

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

Ограничения

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

3
5 10 15

+-

4
4 5 15 5

*--

4
4 5 16 5

No solution

Problem U. Integer approximation ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3.14159265358979
10000

355 113

Problem V. Burned Calendar ≡

Statement

A year calendar is printed using the monospace font according to the following rules:

1) All spaces on the printed calendar are represented by the dot character (ASCII 46).

2) Every month occupies a rectangle of 17 by 8 characters, with the name of the month written in all capital letters starting from the 2nd character of the first line.

3) All days of the months are printed in 4, 5, or 6 columns 2 characters wide and 7 characters high, with one space between the columns. The first day of the week is Monday.

4) Months of the year are arranged in the three rows separated by horizontal and vertical lines of spaces. Each row contains four months. The calendar margins are of 1 space from all sides. Therefore, the whole calendar has size of 73 by 28 characters.

Note that January 1st, 1900 was Monday. Also note that a leap year number is divisible by 4 and not divisible by 100, or divisible by 400. For example, a part of the printed calendar from October to December 2002 may look like this:

A calendar was printed and then burned, with only a small rectangular piece left. Your program must determine to which of years from 1900 to 2100 this piece could belong.

Input file format

Output file format

Constraints

Sample tests

4 4
1..8
....
JUNE
1..8

1903
1914
1925
1931
1942
1953
1959
1970
1981
1987
1998
2009
2015
2026
2037
2043
2054
2065
2071
2082
2093
2099

3 2
1.7
...

0

Problem W. Network Saboteur ≡

Statement

A university network is composed of N computers. System administrators gathered information on the traffic between nodes, and carefully divided the network into two subnetworks in order to minimize traffic between parts.

A disgruntled computer science student Vasya, after being expelled from the university, decided to have his revenge. He hacked into the university network and decided to reassign computers to maximize the traffic between two subnetworks.

Unfortunately, he found that calculating such worst subdivision is one of those problems he, being a student, failed to solve. So he asks you, a more successful CS student, to help him.

The traffic data are given in the form of matrix C, where C_ij is the amount of data sent between ith and jth nodes (C_ij = C_ji, C_ii = 0). The goal is to divide the network nodes into the two disjointed subsets A and B so as to maximize the sum of all C_ij, where i belongs to A, and j belongs to B.

Input file format

Output file format

Constraints

Sample tests

3
0 50 30
50 0 40
30 40 0

90

Problem X. Simple prefix compression ≡

Statement

Many databases store the data in the character fields (and especially indices) using prefix compression. This technique compresses a sequence of strings A₁, ..., A_N by the following method: if there are strings A_i = a_i,1a_i,2...a_i,p and A_{i + 1} = a_i+1,1a_i+1,2...a_i+1,q
such that for some j ≤ min(p, q) a_i,1 = a_i+1,1, a_i,2 = a_i+1,2, ... a_i,j = a_i+1,j, then the second string is stored as [j]a_i+1,j+1a_i+1,j+2... a_i+1,q, where [j] is a single character with code j.

If j = 0, that is, strings do not have any common prefix, then the second string is prefixed with zero byte, and so the total length actually increases.

Input file format

Output file format

Constraints

Sample tests

3
abc
atest
atext

11

2
test
notest

11

Задача Y. Слово из кубиков ≡

Условие

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

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

Ограничения

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

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

Problem Z. Small Addition ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 5

8