Problem A. Binary Witch ≡

Statement

Once upon a time in the silent depths of digital forests there lived a Binary Witch. She was able to forecast weather, telling for any day in the future whether it will be rainy or sunny.

Her magic was based on the following ancient rule: let a₁, a₂, ..., a_N be the sequence of binary digits, where a_i=0 indicates that i-th day was rainy, and a_i=1 - that it was sunny. To predict the weather in day N + 1, consider the t-postfix a_N-t+1, a_N-t+2, ..., a_N consisting of the last t elements. If that postfix is encountered some- where before the position N - t + 1, i.e. if there is such k ≤ N - t, that a_k = a_N-t+1, a_k+1 = a_N-t+2, ..., a_k+t-1 = a_N then the predicted value will be a_k+t. If there is more than one occurrence of t-postfix, then the rightmost one (with maximal k) will be taken. So, to make a prediction, she tried t-postfixes, consequently for t = 13, 12, ..., 1, stopping after the first prediction. If neither postfix was found, she predicted rain ("0"). If prediction for more than one day is needed, it is assumed that all previous days are predicted correctly, so if first predicted value is b, then we make forecast for day N + 2 based on N + 1 values, where a_N+1 = b.

Because the witch was burned long ago, your task is to write a program to per- form her arcane job.

Input file format

Output file format

Constraints

Sample tests

10 7
1101110010

0100100

Problem B. Fool Game ≡

Statement

The game of fool is played with a small set of cards, which includes nine ranks - 6, 7, 8, 9, 0 (10), J (Jack), Q (Queen), K (King), A (Ace) of the four suits each - h (Hearts), s (Spades), d (Diamonds) and c (Crosses). So, for example a queen of spades is denoted Qs, and a ten of diamonds is 0d. One of the suits is declared a trump. During the game, the card beats another card, if either it has the same suit and higher rank, or it is a trump, while the beaten card is not.

In the game, a move proceeds as following. First player puts one of his cards on the desk, and the second player can either beat it with one of his cards, putting his card over it, or take it, if he has no suitable card. If the card is beaten, first player may flip in any of his remaining cards, which has same rank as any card already on the desk. This card, in turn, may be beaten or taken together with all other cards on the desk, etc. For example, if first player has cards 6s6dQhKd, the second player has 6h7h0sQd and hearts are the trumps, then first player can move with Kd, which is beaten with 6h, then flip in 6s, beaten by 0s, then 6d, beaten by Qd and at last Qh, which can not be beaten with 7h, so the second player has to take it.

Your task is to write a program that, given the trump suit and first and second playerTs cards, determines for the first player such a move as to eventually make the second player take.

Your task is to write a program that, given the trump suit and first and second playerTs cards, determines for the first player such a move as to eventually make the second player take.

If there is more than one such move, the program must find one with smallest rank. If there is several moves with smallest rank, program must choose the card with the first suit in the order mentioned in the first paragraph (i.e. h < s < d < c). In the example above, second player could beat Kd with 7h, thus preventing further flips. On the other hand, move of Qh will be immediately taken.

Input file format

Output file format

Sample tests

s
As7h8dJc
Jd8s7c0c

7h

Problem C. Spreadsheet ≡

Statement

You are to write a program emulating a very simple spreadsheet application. It works with a table with 9 rows, from "1" to "9", and 26 columns, from "A" to "Z". Table cells are referenced by names composed of column and row codes, ex. "B1", "S8".

Each cell contains an expression up to 255 characters long. Expressions use integer constants, cell references, parenthesis, operators "+", "-", "*", and "/" (whole division). For example: 567, E8/2, (3+B3)*(C4O1) are all valid expressions. All opera- tors are whole, all arguments and results are guaranteed to be less than 1000000. Divi- sion by zero yields zero.

If the value of the cell referenced by some expression is not defined, it is pre- sumed to be 0 (zero). The situation when two or more cells are mutually dependent on each other is considered a special case of circular reference.

Input file format

Output file format

Sample tests

4
A1=B1+C5
B1=20
C5 =B1 /D7-E1*E1
E1=(3+1)*2

-44

Problem D. PreQueL ≡

Statement

In some simplistic DBMS named PreQueL, the only column type allowed is CHAR(1) (a single character), and furthermore, its values are restricted to English upper- case letters (eAi to eZi). Table may contain up to 9 columns, numbered from 1 to 9. Tables themselves are named with lower-case English letters (eai to ezi).

The only database query possible first joins all the tables, then selects some rows according to conditions in one of two forms: either <column>=<value> or <column1>=<column2>, for example a2=A or b1=c4. All conditions must hold simultaneously, as if they were connected by eANDi operator.

You must write a PreQueL processor, which, given a tables and a set of conditions, will produce query result, i.e. those rows of a join satisfying all the conditions. Resulting rows must be sorted alphabetically.

Input file format

The first line of input file contains of two integers o number of tables T and number of conditions D.

Starting from the second line there are T tables represented with number of rows R_N and number of columns C_N in the first line of a table, which is followed by R_N lines consisting of exactly C_N characters each. D lines with conditions follow the whole set of tables.

Output file format

Constraints

Sample tests

2 2
3 2
AX
BX
BY
2 3
ACD
BCC
a1=b1
a2=X

AXACD
BXBCC

Problem E. Hamming Problem ≡

Statement

Input file format

Output file format

Constraints

Sample tests

7 13 19 100

26590291

Problem F. Circular Area ≡

Statement

Input file format

Output file format

Sample tests

20.0 30.0 15.0 40.0 30.0 30.0

608.37

Problem G. One-move checkmate ≡

Statement

Input file format

Output file format

Sample tests

a3 g2 a1

a2

Problem H. Countryside Highway ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 150 50

4

Problem I. 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 J. Integer approximation ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3.14159265358979
10000

355 113

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