Department of Computer Science, CTU FEE & Czech ACM Chapter

CTU Open Contest 1998

This is an unofficial translation only. It is intented for contestants to get the basic idea about what the problem set could be. Unfortunately, not all the problems are listed here. :-( Learn czech if you want to see all of them. ;-)

The Okurkons Family

Dear contestants:

In this round of ACM Collegiate Programming Contest, we have prepared a couple of practical problems for you. All the problems are real-life problems which the Okurkons Family has to deal with. Beside Tonik Okurkon, the head of the family, you will also meet his pretty wife Juliet, young son Tonicek and little daughter Amalka.

You are to write a set of programs that help the Okurkons to deal with some of their problems. All the programs have to read the standard input, produce some results and send them to the standard output. All the numbers fit into the standard int or integer type, unless specified otherwise.

We strongly believe you will like the competition and find some interesting knowledge during it. Prehaps this knowledge may be useful not only in the Informatics field. Good luck!

The Organization Team

Mince (Coins)

(file name: mince.c, mince.p, mince.C)

Tonik's grandmother was very thrifty and she stored all her savings into golden coins. Before she died she had divided these coins among her grandchildren so Tonik has one of his grandmother's golden coins. In order not the coin to be alone had Tonik several imitations made. The imitations were made so perfectly that it is impossible to say wheter the coin is fake or genuine just by having a look. That's why it was necessary to keep the genuine coin separated from the fake ones.

However Tonik lent Amalka all coins one day. She played with them and as you may expect she shuffled them. There is uneasy task for Tonik now: find the genuine coin. Fortunately he knows that all the fake coins have the same weight different from the weight of the genuine coin. He can use a balance and weights of 1, 2, 2, 5, 10, 20, 20, 50, 100, 200, 200, 500 and 1000 grammes. The weight of a coin (either genuine or fake) is an integer amount of grammes.

Your task is to write a program which for given number of coins calculates a minimum number of weightings necessary to determine the genuine coin and whether it is lighter or heavier than fake coins. One weighting means one comparing left and right side of the balance. It is possible to put any number of coins and weights on either side of the balance.

Input Specification

At the first line there is a positive integer N stating the number of assignments to follow. On each of the following N lines, there is exactly one integer K, K > 2 meaning K coins to examine (including the genuine one).

Output Specification

The program must print exactly one line for each query. The line should contain the text "Minimalni pocet vazeni je X." (Minimum number of weightings is X) where X is the minimum number of weightings necessary to determine the genuine coin.

Sample Input

2
12
3

Output for Sample Input

Minimum number of weightings is 3.
Minimum number of weightings is 3.

Reversi

(file name: reversi.c, reversi.p, reversi.C)

Tchyne (Mother-In-Law)

(file name: tchyne.c, tchyne.p, tchyne.C)

Tonik likes biking very much and makes a lot of trips to various places. Nowadays he is not so enthusiastic and doesn't look forward to another biking trip. The reason of this is his mother-in-law (MIL) who decided to join him on every trip he makes. Can you imagine how happy Tonik was when he learned this decision of his MIL. Fortunately you can help him. After several trips Tonik noticed that his MIL was so exhausted after climbing a certain number of meters that she was unable to go on. That's why he decided to arrange their next trip a little bit different. They both will start from the same spot and either of them has to get to the destination by his/her own. Your task is to write a program to help Tonik decide whether MIL can reach the destination or not.

Input Specification

At the first line there is a positive integer N stating the number of assignments to follow. There are the dimensions of the rectangular map R and C, 1 <= R, C <= 100 on the first line of each assignment. Then exactly R lines follow, each contains C numbers (separated by a space). Number on the i-th position in the j-th row specifies the altitude of the spot on coordinates [i, j]. Coordinates of the left top corner of the map are [1, 1].

The spots are connected by roads which form a rectangular grid. The roads between two neighbour spots are always just up the hill, just down the hill, or level. At the first input line following the map definition, there is exactly one number M specifying the maximum number of meters MIL is able to climb. Next input line contains four numbers R1, C1, R2, C2 separated by a space. [R1, C1] are the coordinates of the initial spot and [R2, C2] are the coordinates of the destination.

Output Specification

The program must print exactly one line for each query. The line should contain the text "Tchyne muze dojet." (MIL can arrive) if it is possible for the MIL to reach the destination. Otherwise, the text must be "Tchyne nedojede." (MIL will not arrive). Assume that MIL does not bike off the roads.

Sample Input

2
3 3
1 2 3
2 3 2
3 2 1
1
1 1 3 3
6 5
1 2 3 4 5
9 8 7 6 5
1 2 3 4 5
1 9 9 9 9
7 5 5 5 5
1 1 1 1 1
8
1 1 6 2

Output for Sample Input

Tchyne nedojede.
Tchyne muze dojet.

Zlomky (Fractions)

(file name: zlomky.c, zlomky.p, zlomky.C)

A little boy Tonicek Okurkon is in the age when children attend elementary school. Most of the children are not quite convinced that this is very useful, however they go sometimes to school for some reason. Imagine the difference between smoking alone somewhere far behind the town and having a cigarette at the school's loo together with other school mates.

The teacher has another trouble with little Tonicek. Attending the school is not the biggest proublem while keeping Tonicek quite seems almost impossible. The teacher was thinking for a long time and finaly found a solution: Tonicek is given a set of mathematical examples with fractions and has to stay in school until he solves them all. Tonicek doesn't like it because more than in fractions is he interested in the last version of Kernel Hacker's Guide and in the newest issue of Playboy. So he would like to have a program to solve the mathematical examples for him. Your task is to write such a program.

Input Specification

At the first line there is a positive integer N stating the number of assignments to follow. On each of the following N lines contains exactly one expression, where expression is:

• ( expression )
• expression operator expression (operator is one of +, -, *, or /)
• number (may be signed)

Expressions are evaluated left to right using standard priorities of operators. After execution of every elementar operation it is possible to represent the result as a quotient of two integer numbers (standard type integer in Pascal and int in C/C++).

Output Specification