Problem A
Tree Recovery

Little Matija liked playing with binary trees very much. His favorite game was 
constructing randomly looking binary trees with capital letters in the nodes. This is an 
example of one of his creations: 

      D 
     / \ 
    /   \ 
   B     E 
  / \     \ 
 /   \     \ 
A     C     G 
           / 
          / 
         F 

To record his trees for future generations, he wrote down two strings for each tree: an 
inorder traversal (left subtree, root, right subtree) and a »leaves-first« order traversal 
(the data in all leaves are printed in left-to-right order, then the leaves are removed 
and the remaining tree is traversed in the same way). A leaf  in a tree is a node with 
no descendants. For the tree drawn above the inorder traversal is ABCDEFG and the 
»leaves-first« order traversal is ACFBGED. 
Now, years later, looking again at the strings, he realized that reconstructing the trees 
was indeed possible, but only because he never had used the same letter twice in the 
same tree. However, doing the reconstruction by hand, soon turned out to be tedious. 
So now he asks you to write a program that does the job for him! 

Input Specification – a.in

The input file will contain one or more test cases. Each test case consists of one line 
containing two strings, representing the inorder traversal and »leaves-first« order 
traversal of a binary tree. Both strings consist of unique capital letters (thus they are 
not longer than 26 characters). Input is terminated by end of file. 

Output Specification – a.out

For each test case print one line containing the tree's level-order traversal (the data in 
all nodes at a given level are printed in left-to-right order and all nodes in level k are 
printed before all nodes at level k+1). 

Sample Input 

ABCDEFG ACFBGED
CBAD CDAB

Expected Output 

DBEACGF
BCAD

Problem B
Connecting Paths

“PATH” is  a game played by two players on an N by N board, where N is a positive 
integer.  (If N = 8, the board looks like a chess board.)  Two players “WHITE” and 
“BLACK” compete in the game to build a path of pieces played on the board from the 
player’s “home” edge to the player’s “target” edge, opposite the home edge.  WHITE 
uses white pieces and BLACK uses black pieces.
For this problem you will play the “referee” for  the game, analyzing boards contain-
ing black and white pieces to determine whether either of the players has won the 
game or if one of the players can win by placing one of their pieces in an unfilled po-
sition. WHITE’s turn is next.
A representation of a board on paper (and in a computer) is an N x N matrix of chara-
cters 'W', 'B', and 'U'; where 'W' represents white pieces, 'B' represents black 
pieces, and 'U' represents unfilled positions on the board.
When we view a matrix representation of the board on paper, WHITE’s home edge is 
the left edge of the board (the first column), and WHITE’s target edge is the right 
edge (the last column).  BLACK’s home edge is the top edge of the board (the first 
row), and BLACK’s target edge is the bottom edge (the last row).  
Thus WHITE wants to build a path from left to right, and BLACK wants to build a 
path from top to bottom.
Two locations on the board are adjacent if one is immediately to the left, to the right 
above, or below the other.  Thus an interior location on the board is adjacent to four 
other locations.  For N>1, corner locations each have two adjacent locations, and for 
N>2, other border locations have three adjacent locations.
A path is a sequence of distinct positions on the board, L0, L1,…, Lk, such that each 
pair Li and Li+1 are adjacent for i=0,…,k-1.  A winning path for a player is a path L0, 
L1,…, Lk filled with the player’s pieces such that L0 is a position on the player’s home 
edge and Lk is a position on the player’s target edge.  It is clear that if one player has a 
winning path then the other player is blocked from having a winning path.  Thus if all 
the squares contain pieces, either there are no winning paths or exactly one of the 
players has at least one winning path.

Input Specification – b.in

Input is a series of game board data sets.  Each set begins with a line containing an 
integer specifying the size N, 0<N<81of the (N x N) game board.  This is followed by 
a blank line and then by N lines, one for each row of the game board, from the top 
row to the bottom row.  Each line begins with character and consists of N adjacent 
characters from the set {'B', 'W', 'U'}.  A blank line separates each non-zero data set 
from the following data set.  The input is terminated by a single line containing a 
board size of zero.

Output Specification – b.out

As referee, for each game board in a series of game boards your program should 
report one of the five types of answers below:
	White has a winning path.
	Black has a winning path.
	White can win in one move.  (White can place a piece in an unfilled position.)
	Black can win in one move.  (White can’t win in one move AND Black can.)
	There is no winning path.

Sample Input

7

WBBUUUU
WWBUWWW
UWBBBWB
BWBBWWB
BWWBWBB
UBWWWBU
UWBBBWW

3

WBB
WWU
WBB

0

Expected Output

White has a winning path.
White can win in one move.

Problem C
Nenavadna funkcija

Nekatere funkcije najlazje opišemo rekurzivno. Taka je tudi naša enoparametricna 
druzina. Funkcije iz te druzine slikajo iz pozitivnih celih števil v pozitivna cela 
števila. Baza rekurzije je predpis F(1)=a. Pri rekurzivnem pravilu locimo dve 
moznosti. Ce je argument sod, potem velja F(2n)=F(n). Ce pa je argument lih, potem 
imamo F(2n+1)=F(n)+F(n+1).
Vaša naloga je napisati program, ki bo dovolj hitro racunal vrednosti funkcije F.

Vhod – c.in

Vsaka vrstica vhodne datoteke vsebuje dve števili: n in a. Število n je med 1 in 
2000000000, število a pa med 1 in 10000. Izracunati je treba vrednost F(n) pri 
pogoju F(1)=a. Zadnja vrstica datoteke vsebuje samo število 0. Testna datoteka ne bo 
vsebovala vec kot 1000 vrstic.

Izhod – c.out

Vsaka vrstica izhodne datoteke naj vsebuje ustrezno vrednost F(n), ce je ta manjša ali 
enaka 1000000000, ali pa besedico overflow, kadar je rezultat vecji od milijarde. 
Izpis naj ne vsebuje odvecnih presledkov.

Primer vhodnih podatkov

13 2
1431655765 1
22369621 9999
0
 
Pricakovan izpis

10
2178309
overflow

Problem D 
Lining Up

``How am I ever going to solve this problem?'' said the pilot. 
Indeed, the pilot was not facing an easy task. She had to drop packages at specific 
points scattered in a dangerous area. Furthermore, the pilot could only fly over the 
area once in a straight line, and she had to fly over as many points as possible. All 
points were given by means of integer coordinates in a two-dimensional space. The 
pilot wanted to know the largest number of points from the given set that all lie on 
one line. Can you write a program that calculates this number? 
Your program has to be efficient! 

Input Specification – d.in

The input file will contain one or more test cases. Each test case consists of a number 
N, where 1 < N < 3000, followed by N pairs of (16-bit) integers. Each pair of integers 
is separated by one blank and ended by a new-line character. No pair will occur twice. 
in the same test case. Input is terminated by N=0.

Output Specification – d.out

The output consists of one integer per test case representing the largest number of 
points that all lie on one line. 

Sample Input 

5
1 1
2 2
3 3
9 10
10 11

0

Expected Output 

3 

 Problem E
Domino Effect

Did you know that you can use domino bones for other things besides playing 
Dominoes? Take a number of dominoes and build a row by standing them on end 
with only a small distance in between. If you do it right, you can tip the first domino 
and cause all others to fall down in succession (this is where the phrase “domino 
effect”' comes from). 
While this is somewhat pointless with only a few dominoes, some people went to the 
opposite extreme in the early Eighties. Using millions of dominoes of different colors 
and materials to fill whole halls with elaborate patterns of falling dominoes, they 
created (short­lived) pieces of art. In these constructions, usually not only one but 
several rows of dominoes were falling at the same time. As you can imagine, timing is 
an essential factor here. 
It is now your task to write a program that, given such a system of rows formed by 
dominoes, computes when and where the last domino falls. The system consists of 
several “key” dominoes connected by rows of simple dominoes. When a key domino 
falls, all rows connected to the domino will also start falling (except for the ones that 
have already fallen). When the falling rows reach other key dominoes that have not 
fallen yet, these other key dominoes will fall as well and set off the rows connected to 
them. Domino rows may start collapsing at either end. It is even possible that a row is 
collapsing on both ends, in which case the last domino falling in that row is 
somewhere between its key dominoes. You can assume that rows fall at a uniform 
rate. 

Input Specification – e.in

The input file contains descriptions of several domino systems. The first line of each 
description contains two integers: the number n of key dominoes (1 ? n ? 500) and the 
number m of rows between them. The key dominoes are numbered from 1 to n. There 
is at most one row between any pair of key dominoes and the domino graph is 
connected, i.e. there is at least one way to get from a domino to any other domino by 
following a series of domino rows. 
The following m lines each contain three integers a, b, and l, stating that there is a row 
between key dominoes a and b that takes l seconds to fall down from end to end. Each 
system is started by tipping over key domino number 1. The file ends with an empty 
system (with n = m = 0), which should not be processed. 

Output Specification – e.out

For each case output a line stating the number of the case ('System #1', 
'System #2', etc.). Then output a line containing the time when the last domino 
falls, exact to one digit to the right of the decimal point, and the location of the last 
domino falling, which is either at a key domino or between two key dominoes. 
Adhere to the format shown in the output sample. If you find several solutions, output 
only one of them. Output a blank line after each system. 


Sample Input 

2 1 
1 2 27 
3 3 
1 2 5 
1 3 5 
2 3 5 
0 0 

Expected Output  

System #1 
The last domino falls after 27.0 seconds, at key domino 2. 

System #2 
The last domino falls after 7.5 seconds, between key dominoes 2 and 3.