Problem A. One-move checkmate ≡

Statement

Input file format

Output file format

Sample tests

a3 g2 a1

a2

Problem B. Countryside Highway ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 150 50

4

Problem C. Market place ≡

Statement

A market has a line of N trading posts selling sunflower seeds. Prospective buyers walk along the line, then at some moment stop and buy the seeds to nibble. Quality of the seeds does not differ substantially among the posts, so the only difference is in price and location of posts. Before trying to enter this market as another seed seller, you have conducted a market research to find out how is the number of buyers influenced by these two factors. The research shows that most buyers follow the same pattern. They walk past some posts noticing and remembering the prices, then after passing K posts return to the one with the lowest price encountered, and make a purchase there, then leave the market. If there are several posts with the equal price, they choose the nearest one in the line. For example, let us assume there are five posts with prices 37, 34, 34, 35, 33. If the buyer with K = 4 walks from the left to right, he sees seeds priced at 37, 34, 34, 35. At this moment, he decides he has seen enough, and goes back to the third post and buys seeds there. Although the second post has the same price as the third, it is a longer walk for the buyer to return there. If the same buyer would enter the line from the right end, he would see prices 33, 35, 34, 34, then stop and return to the fifth post. The number of posts passed before the decision (K) is a function of buyer's greed and patience, and is obviously different for different buyers. The research yielded the average percentage B_K of buyers for all values of K.

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

Output file format

Constraints

Sample tests

5
37 34 34 35 33
10 20 30 30 10

3 33

Problem D. Integer approximation ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3.14159265358979
10000

355 113

Problem E. Multiplication puzzle ≡

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

Output file format

Constraints

Sample tests

6
10 1 50 50 20 5

3650

Problem F. Holey cloth ≡

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

Output file format

Constraints

Sample tests

9 5
.********
.*......*
.*..**..*
.*......*
.********

22

Problem G. Compacting stickers ≡

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:

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

Output file format

Constraints

Sample tests

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

120

Problem H. 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 I. 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 J. 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 K. 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 L. 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 M. 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