Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

KöMaL Problems in Informatics, September 2007

Please read the rules of the competition.

Show/hide problems of signs:

Problems with sign 'I'

Deadline expired on October 15, 2007.

I. 163. Error detecting and correcting codes are frequently used in digital data transfer. A famous code of Richard Wesley Hamming can detect and correct a parity bit error occurring at most once in every block of 7 bits. (A parity error occurs when one bit is changed to its opposite.) To code the message one has to partition the data into blocks of 4 bits and extend each block with 3 checking bits as follows:

(The \oplus sign denotes addition modulo 2, that is ``exclusive or'': x_1\oplus x_2\oplus
\dots \oplus x_n=1 if and only if an odd number of the bits x1,x2,...,xn are equal to 1.)

We then transmit this word k7...k1 consisting of 7 bits. The received message (possibly containing an error) is denoted by f7...f1.

The message is decoded as follows. We recompute the check-sums using the corresponding fj's and the result is compared with the checking bits f4, f2 and f1, that is, for example, f2 with the sum f_7\oplus f_6\oplus f_3. We sum those i indices for which the value of the checking bit fi is incorrect. If this sum is 0, then we consider this word as correct. Otherwise, and this is the main advantage of this method, the sum gives the position of the error, so it can be corrected by simply inverting that bit. Finally we only need to read off the (now correct) bits and have the original message.

Write a program that performs Hamming encoding or decoding. The first argument is en or de, the second argument is the name of the input file, while the third argument is the name of the output. The files consist of 0-1 sequences separated by spaces. The order of the code bits within a code word is arbitrary.

(Checking bit f4 in the first code shows the position of the error is 4, so we invert that bit. The second code is correct. We see that f4 and f2 detected an error, so we should correct the sixth bit f6.)

The source code of your program (i163.pas, i163.cpp, ...) together with a short documentation (i163.txt, i163.pdf, ...) should be submitted, specifying also which developer environment can be used to compile your program.

(10 pont)

solution (in Hungarian), statistics

I. 164. Let us consider the following type of cellular automaton on a 27×27 grid. There are at most two cells living in each square. The uppermost edge of the board is identified with the lowermost one, and similarly, the leftmost with the rightmost. In regular time intervals the whole grid is updated and new cells are formed. Each cell in each step divides into four. The 4 offsprings appear in the 4 neighbouring squares and the parent cell dies. If there are more than 3 newborn cells in a square, they kill each other by threes, until 1 or 2 cells remain.

Write a program to simulate the evolution of the automaton up to N generations. Data is read from the standard input. The first input line is the number of generations N (0\le N\le
1\;000\;000\;000) to simulate. Each of the following 27 lines contains 27 digits (being ``0'', ``1'' or ``2''), encoding the number of living cells in those squares. The output is written to the standard output in the same format.

The simulation should be fast even for large values of N: you can recognize patterns to make the computation faster. We present a only smaller example here.

A full board of size 27×27 can be downloaded from the Internet.

The source code of your program (i164.pas, i164.cpp, ...) together with a short documentation (i164.txt, i164.pdf, ...) should be submitted, specifying also which developer environment can be used to compile your program.

27×27 example input

27×27 example output

(10 pont)

solution (in Hungarian), statistics

I. 165. Column A of the first worksheet of an Excel file contains 0's and 1's. The first few digits are 0's, then there are eight 1's denoting the beginning of the actual data. Then every group of 8 digits encodes the 8 bits of a byte. These bytes came from a text file, so every byte corresponds to an ASCII character. The cells after the last piece of data are empty.

You should devise a formula in cell B1 that restores the original text containing a few hundred ASCII characters at most. Auxiliary computations should be performed on the second worksheet.

Example. If column ``A'' contains

then the output in cell B1 should be 6aA.

The worksheet (i165.xls, i165.ods, ...) together with a short documentation (i165.txt, i165.pdf, ...) should be submitted, also containing the name and version number of the spreadsheet.

(10 pont)

solution (in Hungarian), statistics

Problems with sign 'S'

Deadline expired on October 15, 2007.

S. 28. A version of rummy is played with two standard decks of 52 cards. The object of the game is to dispose of all the cards in your hand. You can get rid of cards as follows.

1.a). One puts one or more sequences down. (A sequence consists of three or more cards of the same suit in consecutive order. Example: Heart 3, 4, 5 and 6. But the group Heart 4, 5 and Diamond 6 is not a sequence.) Or 1.b). One puts one or more sets down (A set consists of three or four cards of the same rank. Example: Heart King, Diamond King and Spade King. But the group Spade Ace, Spade Ace and Club Ace is not a set.)

2. A sequence consists of cards of the same suit. The order of the cards is 2, 3, ..., 9, 10, Jack, Queen, King, Ace or Ace, 2, 3, ..., 9, 10, Jack, Queen, King, so Ace is either the first or the last card of a sequence. Valid sequences are, for example: Club 10, Club Jack, Club Queen, or Heart Ace, Heart 2, Heart 3 and Heart 4. The sequence Spade King, Spade Ace and Spade 2 is, however, invalid.

3. A Joker can substitute any of the cards in a sequence or a set, however, the number of non-Jokers must be greater than the number of Jokers. For example, Heart 9, Heart 10, Joker, Joker and Heart King is a valid sequence. The sequence Joker, Spade 4 and Joker is invalid. Heart 5, Joker, Joker and Heart 8 is also an invalid sequence.

Players put down cards from their hands and, optionally, they can also rearrange cards already on the table according to the above rules. Example: Heart 5, Diamond 5, Club 5 and Spade 5 are on the table in a group, while Club 4 and Club 6 are in a player's hand. The player then can form a group of Heart 5, Diamond 5 and Spade 5 on the table, and another group of Club 4, 5 and 6 - this way the player can put down both cards simultaneously.

The next player can not take any card from the table. If he or she is unable to put down any cards, then that player draws one card from the talon (that is, from the remainder of the deck after the deal).

You should create a program s28 that gets rid of as many cards as possible. The first input parameter of your program is the name of a file describing cards on the table. The second input parameter points to a file containing cards in the hand of the player. The standard output of the program is the content of the table (after cards have been put down and possibly rearranged) and the remaining cards in the player's hand.

Suits of the cards are abbreviated by their first letters H(eart), D(iamond), C(lub) and S(pade). The ranks of the cards are denoted by 2, 3, 9, 0, J(ack), Q(ueen), K(ing) and A(ce). So, for example, H4 means Heart 4, C0 means Club 10 and SQ means Spade Queen. Jokers have no suits, and they are denoted by JJ.

The first input file contains cards on the table. Each line contains a group of cards separated by spaces and in increasing order. (If there are no cards on the table, then the input file is empty.) The second input file contains cards in the player's hand. It has only one line and the name of the cards are separated by spaces. This file can not be empty, it contains at least 1 card.

The output first gives cards on the table, one group per line. Cards are separated by spaces and are in increasing order. The second part of the output finally gives cards that could not be disposed of. This part consists of a single line and cards are separated by spaces.

Example. The file a.txt contains cards on the table:

K4 JJ K6 K7
TA T2 T3 T4 T5

The file b.txt contains cards in the player's hand:

K5 K5 JJ TK T0

Upon executing s28 a.txt b.txt, the output is:

K4 K5 K6 K7
T2 T3 T4
K5 T5 JJ

The source code (s28.pas, s28.cpp, ...) of the program together with a short documentation (s28.txt, s28.pdf, ...) should be submitted, specifying also which developer environment can be used to compile your program.

(10 pont)

solution (in Hungarian), statistics


Upload your solutions above