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

KöMaL Problems in Informatics, November 2014

Show/hide problems of signs:

Problems with sign 'I'

Deadline expired on December 10, 2014.

I. 358. In the minesweeper game one has to locate, or, more precisely, avoid, the $\displaystyle K$ ($\displaystyle 0\le K\le N\times N/2$) mines on a board of size $\displaystyle N\times N$ ($\displaystyle 2\le N\le 50$). The content of these $\displaystyle N^2$ cells is initially hidden, but cells can be revealed by clicking on them. The game is immediately lost if we click on a cell containing a mine. Otherwise, a number between 0 and 8 is displayed in the newly discovered cell, showing the number of neighboring mines relative to this cell. If the newly discovered cell contains no mines, then all of its neighbors are automatically revealed, and this process is iterated by revealing the empty neighbors of the neighbors and so on. The game is won when all cells without mines are revealed.

The example shows one step of a game; Aktuális állás'' is the current position, A következő lépés'' is the next step, A rejtett aknák'' are the hidden mines, Sor'' is row and Oszlop'' is column.

Your program i358 should generate a mine field and play a game with the user.

1. Read the values of $\displaystyle N$ and $\displaystyle K$, then solve the following tasks.

2. Generate the board with $\displaystyle K$ mines placed randomly: *'' denotes a mine, while .'' is an empty cell.

3. In order to test your program, one should be able to choose between Teszt (= test) and Játék (= game) modes. In the Teszt mode the mines should be visible, but in the Játék mode they should be hidden.

4. Read a valid row and column coordinate pair, then - based on the content of that cell - display an appropriate answer as follows.

$\displaystyle a)$ If the selected cell contains a mine, then display Bumm! and stop the game.

$\displaystyle b)$ If the selected cell does not contain a mine, then - by using the rules described above - display the current status of the revealed and still unknown cells.

5. The program should proceed and read the guesses until the user has determined the number of neighbors of all the empty cells. When this happens, the program should display a Nyertél! (= You won) message.

6. Before each user guess, your program should display the number of unknown cells and the number of the actual guess.

The source code (i358.pas, i358.cpp, ...) of your program with a brief documentation (i358.txt, i358.pdf, ...) of your solution should be submitted in a compressed file i358.zip, also specifying the developer environment to use for compiling your source.

(10 pont)

solution, statistics

I. 359. In this task you are going to analyze the data of a tennis match. The match result and its current state are determined as follows.

1. A match is finished if one player wins at least 3 sets.

2. To win a set, the player needs to win at least 6 games such that there is a margin of at least 2 points over the opponent. For example, a set can be won by 6:1, 6:4, 7:5 or 11:9, but it cannot be won by 6:5 or 7:6 -- there are no short sets'' in the present exercise.

3. A game is won if the player has won at least 4 points provided that there is a margin of at least 2 points over the opponent.

4. For the purposes of the present exercise, a point is always won by either the server (A) or the receiver (F).

The match starts with the first player being the server. Within the same game, the same player is the server. In the next game, the other player becomes the server irrespective of the current player scores.

The first column of the spreadsheet labdamenetek (= Points) should contain for each point - up to a certain standing of the match - whether it was scored by the server (A) or the receiver (F). There can be at most 1000 points in a match, and a letter A in the $\displaystyle n$th row of the sheet indicates that the $\displaystyle n$th point was scored by the server. After the match is over, no further points are stored in the sheet, in other words, the cells are empty below the last A or F letter.

The állás (= Standing) sheet should contain the actual standing of the match, according to the last row of the sheet labdamenetek, containing the standing of the won sets, the results of the earlier sets, and the standing of the games within a given set, finally, the standing within the game. The first row of your table should contain a heading according to the description above. To obtain the maximum number of points for this exercise, you should present the standings within a game in the usual format.

The first 4 columns of your sheet teszt (= Test) should contain some values for which the állás sheet gives correct results if a column from the teszt sheet is pasted into the first column of the labdamenetek sheet.

Your solution should not contain any macros or user-defined functions. Beginning with the second column of the labdamenetek sheet, you may use any number of auxiliary cells.

In the example, the állás sheet is shown: Első'' is first, Második'' is second, Játékos'' is player, játszma'' is set and Nyert játszmák'' is the sets won, finally, Aktuális játék'' means the actual game.

Your sheet (i359.xls, i359.xlsx, i359.ods, ...) with content specified above, together with a short documentation (i359.txt, i359.pdf, ...) also describing the name and version number of the spreadsheet application, should be submitted in a compressed file (i359.zip).

(10 pont)

solution, statistics

I. 360. In the advertisements nowadays one can see not only washing powders, concerts or tabloid newspapers, but also museums and educational institutions. In this exercise you should design a KöMaL advertisement that can be placed e.g. on the public transportation vehicles. In order to present your realistic plan, you should put an advertisement on the troli.jpg image (source: http://iho.hu/img/galery/130523-iktroli.jpg).

However, many people freely use images downloaded from the Internet, without specifying the source. Hence, watermarks are often used to identify the creator of the image. Watermarks can contain texts or graphics. The example below falls into the first category:

You should create a watermark for our journal that could be placed on the images of komal.hu having size at least $\displaystyle 800\times 600$ pixels. You should put your watermark on any of the images on the page http://www.komal.hu/hirek/2004-09/imo2004/beszamolo.h.shtml. The watermark should be clearly visible but should not obscure the original content. You can use any freely available tools to complete your task.

The description of your solution (i360.pdf) and your images should be submitted and uploaded in a single compressed file (i360.zip) also containing the name and version number of the software used, and a sufficiently accurate explanation to reproduce your advertisement and watermark on the given image.

(10 pont)

solution, statistics

Problems with sign 'S'

Deadline expired on December 10, 2014.

S. 93. There are $\displaystyle N\le 100\; 000$ athletes participating in a training program. Each athlete has to cycle round a lake, then row across the lake and back, in this order. Due to financial reasons however the sports club only has a single bicycle and a single boat. This means that only one athlete can cycle at any given moment, and the same restriction holds for the rowing. For each athlete they know how many hours it takes to cycle round the lake, and how many hours (s)he needs to row across the lake. They want to finish the training program as soon as possible, hence we are interested in the minimum total time to do this.

Your program should read $\displaystyle N$ from the first line of the standard input, then the $\displaystyle b_i$, $\displaystyle e_i$ quantities from the following $\displaystyle N$ lines - these values stand for the cycling and rowing times in hours, respectively, and they are separated by a space. In the first and only line of the standard output, your program should write the minimum time in hours so that everybody can finish the training program.

In the example, Példa bemenet'' is a sample input, and Példa kimenet'' is the corresponding output.

Explanation: the correct order is 3, 1, 2.

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

The source code (s93.pas, s93.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s93.txt, s93.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file s93.zip.

(10 pont)

solution, statistics

\$Var(Body)