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

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

Условие

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

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

Первая строка входного файла содержит целые положительные числа N и M — ширина и высота участка шахматной доски соответственно.

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

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

Ограничения

1 ≤ N * M ≤ 30

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1
A1
2
1 2
No solution
3
3 4
A1 B3 C1 A2 B4 C2 A3 B1 C3 A4 B2 C4

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

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

Условие

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

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

Первая строка входного файла содержит число N — количество элементов последовательности. Вторая строка содержит N целых чисел Ai — элементы последовательности.

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

Выведите в выходной файл текстовую строку, состоящую из знаков арифметических операций, не разделяя их пробелами. При этом '+' должен соответствовать сложению, '-' - вычитанию, '*' - умножению. Если искомой последовательности не существует, выведите 'No solution'. Если существует несколько решений, выведите любое из них.

Ограничения

2 ≤ N ≤ 8, −10 ≤ Ai ≤ 10

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 10 15
+-
2
4
4 5 15 5
*--
3
4
4 5 16 5
No solution

Problem C. Integer approximation

Author:Far-Eastern Subregional
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:8 Mb

Statement

The FORTH programming language does not support floating-point arithmetic at all. Its author, Chuck Moore, maintains that floating-point calculations are too slow and most of the time can be emulated by integers with proper scaling. For example, to calculate the area of the circle with the radius R he suggests to use formula like R * R * 355 / 113, which is in fact surprisingly accurate. The value of 355 / 113 = 3.14159... is approximating the value of π with the absolute error of only about 10-7. You are to find the best integer approximation of a given floating-point number A within a given integer limit L. That is, to find such two integers N and D (1 ≤ N, D ≤ L) that the value of absolute error |A - N / D| is minimal.

Input file format

The first line of input file contains a floating-point number A with the precision of up to 15 decimal digits. The second line contains the integer limit L.

Output file format

Output file must contain two integers, N and D, separated by space.

Constraints

0.1 ≤ A < 10, 1 ≤ L ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3.14159265358979
10000
355 113

Problem D. Burned Calendar

Author:Far-Eastern Subregional
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:8 Mb

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:

.OCTOBER...........NOVEMBER..........DECEMBER.........

....7.14.21.28........4.11.18.25........2..9.16.23.30.

.1..8.15.22.29........5.12.19.26........3.10.17.24.31.

.2..9.16.23.30........6.13.20.27........4.11.18.25....

.3.10.17.24.31........7.14.21.28........5.12.19.26....

.4.11.18.25........1..8.15.22.29........6.13.20.27....

.5.12.19.26........2..9.16.23.30........7.14.21.28....

.6.13.20.27........3.10.17.24........1..8.15.22.29....

......................................................

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

The first line of the input file contains integer numbers N and M, separated by spaces - the size of the piece. The following M lines contain N characters each - the piece of calendar.

Output file format

Output file must contain an ordered list of year numbers, one year per line. If given piece could not belong to any calendar, output must contain a single integer 0 (zero).

Constraints

2 ≤ N, M ≤ 10

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
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
2
3 2
1.7
...
0

Problem E. Network Saboteur

Author:Far-Eastern Subregional
Input file: input.txt   Time limit:3 sec
Output file: output.txt   Memory limit:8 Mb

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 Cij is the amount of data sent between ith and jth nodes (Cij = Cji, Cii = 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 Cij, where i belongs to A, and j belongs to B.

Input file format

The first line of input file contains a number of nodes N. The following N lines, containing N space-separated integers each, represent the traffic matrix C.

Output file format

Output file must contain a single integer - the maximum traffic between the subnetworks.

Constraints

2 ≤ N ≤ 20; 0 ≤ Cij ≤ 10000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
0 50 30
50 0 40
30 40 0
90

Problem F. Simple prefix compression

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

Statement

Many databases store the data in the character fields (and especially indices) using prefix compression. This technique compresses a sequence of strings A1, ..., AN by the following method: if there are strings Ai = ai,1ai,2...ai,p and Ai + 1 = ai+1,1ai+1,2...ai+1,q

such that for some j ≤ min(p, q) ai,1 = ai+1,1, ai,2 = ai+1,2, ... ai,j = ai+1,j, then the second string is stored as [j]ai+1,j+1ai+1,j+2... ai+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

First line of input file contains integer number N, with following N lines containing strings A1 ... AN

Output file format

Output file must contain a single integer — minimal total length of compressed strings.

Constraints

1 ≤ N ≤ 10000, 1 ≤ length(Ai) ≤ 255.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
abc
atest
atext
11
2
2
test
notest
11

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

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

Условие

Имеется N кубиков, на гранях которых написаны буквы. Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов, и если да, то вывести номера использованных кубиков. При этом каждый кубик можно использовать только один раз. Если решений несколько, выдать любое из них.

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

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

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

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

Ограничения

1 ≤ N, K ≤ 12.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
2 5 3 4

Problem H. Small Addition

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

Statement

You are to write a problem that reads two positive integers A and B with no more then five decimal digits and outputs their sum A+B.

Input file format

First line of input file contains two integers A and B.

Output file format

Output file must contain a single integer C = A+B.

Constraints

-10000 <= A, B <= 10000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 5
8

0.065s 0.004s 21