Problem A. 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 B. 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 C. 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 D. Longest Ordered Subsequence ≡

Statement

A numeric sequence of a_i is ordered if a₁ < a₂ < ... < a_N. Let the subsequence of the given numeric sequence (a₁, a₂, ., a_N) be any sequence (a_i1, a_i2, ., a_iK), where 1 ≤ i₁ < i₂ < ... < i_K ≤ 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

Output file format

Constraints

Sample tests

7
1 7 3 5 9 4 8

4

Problem E. Falling Cards ≡

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 (x_i, y_i) to (v_i, w_i). 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 (x₁, y₁)-(v₁, w₁) 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

Output file format

Constraints

Sample tests

3 100
10 10 50 40
10 0 50 30
20 90 20 20

1 3

Problem F. Very Simple Problem ≡

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

Output file format

Constraints

Sample tests

4 4
1 1 1 2
5 900 21 40
10 10 9 10
3 4 3 5

3