## Problem A. One-move checkmate ≡

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

### Statement

The chess endgame "a king and a queen versus a king" is known to be easy victory for the side that has a queen. The position in such an endgame is described by the locations of three figures: the white king, the white queen, and the black king. Locations are written in a usual chess notation, constructed from a letter from "a" to "h", which determine vertical line, and the digit from 1 to 8, which determine horizontal line of the location. Given the position described, you are find a move for the white queen by which the black king will be checkmated, or determine that no such a move exists.

### Input file format

The input file contains three two-character locations for the white king, white queen, and black king, in that order, separated by spaces. The input position is a valid chess position for the white's turn, i.e. all figures occupy different spaces, kings are not located in the neighboring squares, and the black king is not under the check.

### Output file format

Output file must contain the two-character location - destination square for the white queen's move. If checkmating move does not exist, output file must contain the string "no". If there is more than one checkmating move, you may output any one of them.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
a3 g2 a1
a2

## Problem B. Countryside Highway ≡

 Author: unknown Input file: input.txt Time limit: 15 sec Output file: output.txt Memory limit: 200 Mb

### Statement

Regional government wishes to build a new highway across the region, and it seems that the best route for the highway goes across the Kvadratnaya village.

The village consists of the N x N square estates.

All estates have a size of 100 by 100 meters.

Therefore, in the coordinate system tied to the village, the southwestern corner of the village has coordinates (0, 0), and northeastern corner - coordinates (N*100, N*100).

The highway will cross the village form the west to the east side, cutting through several estates. The government decided to compensate owners of those estates, and to estimate the necessary expenses one should calculate the number of estates crossed by the highway. Given the village size N and the coordinates of the points where the highway crosses eastern and western borders of the village, you must find the number of estates.

You can assume, for the purpose of increasing the financial appeal of the highway project, that the highway is a straight line (i.e. has zero width).

If the highway just touches the edge of an estate, it is still considered a crossing. The highway is a line between points (0, W) and (100*N, E).

### Input file format

In the input file, there are three integers, N, W and E, separated by spaces.

### Output file format

Output file must contain a single integer - the number of estates crossed by the highway.

### Constraints

1 <= N <= 100

0 <= W, E <= 100*N

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 150 50
4

## Problem C. Market place ≡

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

### Statement

You are to determine the optimal market strategy (i. e. the price and location of the new post which maximizes anticipated average income) under the assumptions that half of the clients walk in the direction from the first post to the Nth and another half - from the Nth post, to the first, and that they behave according to the pattern above.

### Input file format

The first line of the input file contains the number of existing posts N. The second line contains N integers pi - the prices for the posts. The third line contains N integers - the values of BK for each K. All numbers in a line are separated by spaces.

### Output file format

The output file must contain two integers - L and P. L (1 ≤ L < N) is the number of the existing post after which the new one should be placed (You are not allowed to place your post first or last in the line). The second number P is the optimal price. If there is more than one optimal solution, you should choose the one with the minimal L, and between them - the one with minimal P.

### Constraints

2 ≤ N ≤ 100, 1 ≤ pi ≤ 9999, 0 ≤ Bk ≤ 99, B1 + ... + BN = 100

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5
37 34 34 35 33
10 20 30 30 10

3 33

## Problem D. 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 E. Multiplication puzzle ≡

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

### Statement

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.

The goal is to take cards in such order as to minimize the total number of scored points.

For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring 10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000

If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be 1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.

### Input file format

The first line of the input file contains the number of cards N. The second line contains N integers ai, separated by spaces.

### Output file format

Output file must contain a single integer - the minimal score.

### Constraints

3 ≤ N ≤ 100, 1 ≤ ai ≤ 100

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
6
10 1 50 50 20 5

3650

## Problem F. Holey cloth ≡

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

### Statement

Several pieces of cloth are laid out on the table without overlapping each other. These pieces contain many holes, some so big that entire other piece of cloth may fit into them. Digital black-and-white image of the tabletop was taken, on which areas covered by cloth are represented with '*'s and not covered areas with '.'s. A single piece of cloth is thus represented with 4-connected area of '*'s - i.e., a group of '.'s located next to each other horizontally or vertically, but not diagonally. For example, on the following image there are three pieces - one without holes, and two with one hole each - first has area of 8, and the second - area of 12.

.***..***
.*.*.**.*
.***.*.**
*...**.*.

Your goal is to find the piece with the most holes in it. The hole is a 4- connected area of '.'s completely surrounded with '*'s. If several pieces have the same number of holes, you must select the one with the smallest area.

### Input file format

In the first line of input file there are two numbers W and H, separated by spaces. Next H lines contain W characters each. Characters in these lines are either '*' (ASCII 42) or '.' (ASCII 46).

### Output file format

The output file must contain a single integer - the area of the smallest of most holey pieces. If there are no pieces with the holes, the output file must contain zero.

1 ≤ W, H ≤ 100

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
9 5
.********
.*......*
.*..**..*
.*......*
.********

22

## Problem G. Compacting stickers ≡

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

### Statement

The text on a sticker consists of words formed from small and capital Latin letters. Words are separated by spaces, line breaks, and/or the following punctuation marks: ",", ".", "!", "?".

There may be any number of spaces and empty lines before and after the words, but there is no more than one punctuation mark after each word. Sticker is printed with monospace font, so every character occupies on the paper a rectangular area of fixed size. Sticker itself is a minimal rectangle enclosing the text plus a margin of one character in width.

Many copies of the sticker are to be printed, and to minimize paper consumption the sticker should be made as small in area as possible. Consider, for example, the sticker with the following text:

Our pink elephants have great size and a small price. Buy our elephants!

Printed in one line, this sticker will have an area of (72 + 2) * (1 + 2) = 222 characters. On the other hand, if printed in four lines, like this:

 ···················· ·Our·pink·elephants· ·have·great·size···· ·and·a·small·price.· ·Buy·our·elephants!· ····················

the sticker will only require (18 + 2) * (4 + 2) = 120 characters.

You objective is, given the text of a sticker, to break it into lines so as to achieve the smallest possible area for it. Line break may be inserted after any word or punctuation mark, but not before a punctuation mark. One space must separate each word from the preceding word or punctuation on the same line. You do not have to preserve other spaces or line breaks in the input file.

### Input file format

The input file contains one or more lines of the sticker text. Text contains only the following characters: "A" to "Z", "a" to "z", ",", ".", "!", "?", spaces and line ends. The text always contains some non-space characters, and the first of them is always a letter.

### Output file format

Output file must contain a single integer number - the area of the smallest sticker.

### Constraints

The text length is less or equal than 10000 characters.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
Our pink
Elephants
have great size and a
small price .

120

## Problem H. Tetris alphabet ≡

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

### 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

The first line of input file contains integer N - number of rows. Following N lines contain 20 characters each, with characters that are either a letter from 'A' to 'Z' or the dot character (ASCII 46), representing an empty cell.

### Output file format

Output file must contain a string of letters indicating the order in which figures fell down. If there is more than one order, lexicographically smallest one must be printed. Input data will guarantee that at least one nonempty order exists.

0 ≤ N ≤ 50

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
6
...........XX.......
..........MMMM......
..........K.........
........KKK.........
.....ZAAA.FFF.......
.....ZZZA..F.B......

BFZAKMX

## Problem I. 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 J. 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).

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 K. Longest Ordered Subsequence ≡

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

### Statement

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ., aN) be any sequence (ai1, ai2, ., aiK), where 1 ≤ i1 < i2 < ... < iK ≤ N. For example, the sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences of this sequence are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

### Input file format

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces.

### Output file format

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

1 ≤ N ≤ 1000

### Sample tests

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

4

## Problem L. Falling Cards ≡

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

### Statement

It is hard to make the playing card stand on its edge, however, some patient person managed to put N of them upon the desk in such a way that each cards stands on its shorter edge. The top-down view of that desk with cards upon it can be represented with the set of line segments with coordinates (xi, yi) to (vi, wi). The segments do not intersect.

The first card falls flat on its side, causing any card it touches to fall down also. The angle between vector (x1, y1)-(v1, w1) and the falling direction of the first card is equal to 90 degrees (measured counter-clockwise). If card A touches card B, the direction of B's fall is chosen so that the continuation of the direction vector does not cross the line containing segment A. Input data are guaranteed to never contain:

1) a card falling exactly perpendicular to the other and

2) a falling card that touches more than one of still standing cards.

Your program must determine which cards will fall, and which shall remain standing.

### Input file format

The first line of input file contains a numbers N H - the number of cards and the floating point height of a card. Each of the following N lines contains four floating-point numbers xi yi vi wi - coordinates of cards separated by spaces.

### Output file format

The output file must contain the list of fallen cards' numbers, sorted in increasing order and separated by spaces.

1 ≤ N ≤ 100

### Sample tests

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

1 3

## Problem M. Very Simple Problem ≡

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

### Statement

During a preparation of programming contest, its jury is usually faced with many difficult tasks. One of them is to select a problem simple enough to most, if not all, contestants to solve.

The difficulty here lies in diverse meanings of the term "simple" amongst the jury members. So, the jury uses the following procedure to reach a consensus: each member weights each proposed problem with a positive integer "complexity rating" (not necessarily different for different problems). The jury member calls "simplest" those problems that he gave the minimum complexity rating, and "hardest" those problems that he gave the maximum complexity rating.

The ratings received from all jury members are then compared, and a problem is declared as "very simple", if it was called as "simplest" by more than a half of the jury, and was called as "hardest" by nobody.

### Input file format

The first line of input file contains integers N and P, the number of jury members and the number of problems. The following N lines contain P integers in range from 0 to 1000 each - the complexity ratings.

### Output file format

Output file must contain an ordered list of "very simple" problem numbers, separated by spaces. If there are no such problems, output must contain a single integer 0 (zero).

1 ≤ N, P ≤ 100

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 4
1 1 1 2
5 900 21 40
10 10 9 10
3 4 3 5

3

0.109s 0.005s 31