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

Условие

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

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

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

Ограничения

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

1 1

A1

1 2

No solution

3 4

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

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

Условие

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

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

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

Ограничения

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

3
5 10 15

+-

4
4 5 15 5

*--

4
4 5 16 5

No solution

Problem C. Integer approximation ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3.14159265358979
10000

355 113

Problem D. 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 E. 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 F. 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

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

Условие

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

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

Ограничения

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

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

Problem H. Small Addition ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 5

8