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

# KöMaL Problems in Informatics, March 2016

Show/hide problems of signs:

## Problems with sign 'I'

Deadline expired on April 11, 2016.

I. 397. (É.) A chess tournament with 32 participants is organized as follows. In the first round, the organizers create some groups, then they play a round-robin tournament within each group (that is, everybody plays against any other player in their group). Initially each contestant has 100 points. The winner of each game gets 5% of the points of the opponent rounded up to the nearest integer. The points of the defeated player are not changed. In case of a tie, the game is repeated.

The results after the first round together with the Hungarian players' names are found in the text file sakk.txt (downloadable from our web page). Each line of the file corresponds to one player and contains the following data: player's points, family name, given name(s)—separated by a space. The file does not contain characters with diacritical marks, nor unnecessary lines or spaces, and no name prefixes (such as Dr or Mr). A short sample of the file is displayed below:

In the second round, they play a single-elimination tournament (consisting of several turns), which is explained below. The players are sorted according to descending points, and the first player plays with the last one, the second player with the second last, and so on. Players having the same number of points are sorted into alphabetical order. Players in the pairs obtained this way play one game against each other in the first turn. The winners get extra points as described above, while the defeated players are out of the tournament. Then the organizers again sort the players. In the second turn the remaining players again play one game against each other. This process is repeated until the last game.

Create your program i397 to solve the following tasks. Before displaying your solution, the actual problem number should appear on the screen such as ,,Task #3''. Instead of displaying a player's given name, only its first character should appear followed by a dot. When a Hungarian name begins with a digraph, both characters should be displayed.

1. Import and store data from the file sakk.txt.

2. Display the players' names on the screen in the original order by using the following format:

3. Simulate the games between pairs of players in the second round so that the chance of winning should be proportional to the current points of the player. More precisely, you should do the following. Suppose the two players have points $\displaystyle A$ and $\displaystyle B$. Generate a random integer between 1 and $\displaystyle A+B$ inclusive. The first player is the winner, if the random integer is between $\displaystyle 1$ and $\displaystyle A$; the second player is the winner, if the random integer is between $\displaystyle A+1$ and $\displaystyle A+B$. Your Boolean function ElsoNyer should yield true'' if the first player wins, and false'' if the second wins. The input of this function is the pair of points $\displaystyle (A,B)$.

4. Play the first turn of the second round by using the previous Boolean function. Display the players' data at the end of the turn. Each line should contain a pair of players by using the format given in Task 2 above. Lines should be separated by the string (---).

5. Determine who scored the maximum points against whom in the first turn of the second round. You should display this in a sentence such as ,,Kiss-Kerekes E. (396) scored the maximum points (18) against Kovacs A. Gy. (345)''.

6. Simulate also the second turn of the second round. Results after the 8 games should be written in the file kor2.txt together with the pairing described in Task 4.

7. By using an abbreviated name format and separated by a comma, list those players who are eliminated in the second turn but still scored more points than the player with minimum points qualified for the third turn.

8. Simulate the remaining turns and display data for the two players in the final, and the winner of the tournament.

The source code and a short documentation of your program—containing a brief description of your solution, and the name of the developer environment to compile your code—should be submitted in a compressed file i397.zip.

(10 pont)

solution, statistics

I. 398. There are some ATMs for cash withdrawal and deposit in the foyer of a bank. If someone wants to access the ATMs when the bank is closed, their bank card is scanned and, for security reasons, some data are logged upon entering or exiting the foyer. The tab-separated and UTF-8-encoded text file naplo.txt containing the log file of a certain day after banking hours can be downloaded from our web page.

Open the file naplo.txt in a spreadsheet application such that the first piece of data is put in cell A1, then save this sheet as i398 by using the default application file format.

The log file records every event (hour, minute), the type of the event (1, $\displaystyle -1$, 2 and $\displaystyle -2$ denote entering, exiting, cash deposit and cash withdrawal, respectively), the 5-digit card number, and the amount of money (if applicable).

Example:

You should solve the following tasks by using formulae, functions and references. Since the number of events is unknown in advance, your solution should be able to handle 150 possible events.

In your solution you can perform auxiliary computations in any number of columns if they contain some explanation. Answers to the following questions should be collected in a separate sheet.

– What is the total cash deposit and withdrawal based on the log file?

– Which bank card was used to withdraw the largest amount of money? If the maximum amount is not unique, give the card corresponding to the earliest event.

– What is the maximum number of people in the foyer at the same time? What is the earliest time such that this maximum occurred?

– How many different bank cards were used in the transactions?

– How many bank cards were used to perform cash deposit and also withdrawal?

– On a separate sheet and by using a nicely formatted bar chart with legends, display the number of transactions in each hour between 20:00 and 08:00.

The spreadsheet and a short documentation, containing the name and version number of the spreadsheet application, should be submitted in a compressed file i398.zip.

(10 pont)

solution, statistics

I. 399. The first spreadsheet application, VisiCalc, was created by Dan Bricklin and Bob Frankston in 1979. Although the program development ended in 1985, the application (with text-based interface and occupying only approx. 28 KB) can still be found on the Internet at http://www.bricklin.com/history/vcexecutable.htm. It can directly be run under 32-bit Windows 7; under Windows 10, for example, some emulator (like DosBox) is necessary. The VisiCalc manual is available at http://toastytech.com/manuals/VisiCalc%201.1.pdf.

In this task you are going to process data of a grocery store from the first half of 1979. Columns A and B contain the code of sold items in chronological order, and the sold amount. The range F2:H8 contains the item codes, names and unit prices.

1. By using VisiCalc, open the file visi.vc and solve the following tasks. The sheet containing your solution should be saved as noszt.vc.

2. By using a function in cell C2, determine the unit price of the item in cell A2.

3. By using a formula in cell D2, compute the total price of the item whose quantity is found in B2 and unit price in A2.

4. Copy the formula in cells C2 and D2 to the cells beneath them up to line 50.

5. Determine the sold amount for each item in the range I2:I8. You can use auxiliary columns to the right of column L.

6. Determine the income from each item in the range J2:J8.

7. Fill the range F9:J9 with a horizontal dashed line.

8. By using a formula in the range G10:G13, determine the number of items that can be purchased, the average income from the items, the total income, and the maximum income.

9. Set the cell width to 11 characters.

10. Display in column K the relative income for each item by using ,,$\displaystyle \mathtt{*}$'' characters so that the maximum income is represented by 10 ,,$\displaystyle \mathtt{*}$'' characters.

The file noszt.vc should be submitted in a compressed file i399.zip.

(10 pont)

solution, statistics

## Problems with sign 'I/S'

Deadline expired on April 11, 2016.

I/S. 7. We are given a $\displaystyle 5\times 5$ grid. Each square either contains one candy or is empty. There are altogether $\displaystyle 0\le K\le 22$ empty squares with $\displaystyle K$ even, the rest of the squares contain candies. We know that the top left field $\displaystyle (1;1)$ and the bottom right field $\displaystyle (5;5)$ contain candies. Two kids would like to eat candies: one starts from $\displaystyle (1;1)$ and the other from $\displaystyle (5;5)$. First they eat the candies at their actual position, then they simultaneously take a step to one of the adjacent squares (adjacent'' here means sharing an edge'') containing a candy. They eat those candies and take another step following the above rule, then repeat the process. Their goal is to collect all candies and meet, but they need to eat the last candy together. They should only meet in the very last step. You should determine the number of ways they can traverse the grid (they cannot visit any square twice since they only step on squares with candies).

Your program should read the value of $\displaystyle K$ from the first line of the standard input. The following $\displaystyle K$ lines contain the missing candy positions. The first and only line of the standard output should contain the number of possible grid traversals. If the grid cannot be traversed, a 0'' should appear. Two traversals are different if there is at least one kid with a different step at some point.

Explanation. There are 4 missing candies in the middle row. The kids should meet in this row in the $\displaystyle 5^\mathrm{th}$ column. It is easy to see that in this case their path is unique.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file is7.zip.

(10 pont)

solution, statistics

## Problems with sign 'S'

Deadline expired on April 11, 2016.

S. 106. We are given a country with $\displaystyle N$ ($\displaystyle 1\le N\le 17$) cities. There are $\displaystyle M$ cities connected by bidirectional highways. The goal is to organize the maximum number of scientific conferences having different types. A conference of a given type can be organized in more cities, but one city can only host one conference. People in a given city can only visit the conference in their city or in an adjacent city. We would like to organize the maximum number of conference types such that people from any city can visit any conference type. For example, organizing only one type of conference is always possible: each city hosts the same type of conference.

Your program should read the values of $\displaystyle N$ and $\displaystyle M$ from the first line of the standard input. The following $\displaystyle M$ lines describe the highways connecting the cities. The first and only line of the standard output should contain the maximum number of different conference types that can be organized in this country.

Explanation. Cities 1 and 4 host a conference of type $\displaystyle A$, while cities 2 and 3 host a conference of type $\displaystyle B$.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file s106.zip.

(10 pont)

solution, statistics

\$Var(Body)