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 2014

Show/hide problems of signs:

## Problems with sign 'I'

Deadline expired on October 10, 2014.

I. 352. The figure (Példa a lakótelepre'') shows a rectangular area consisting of $\displaystyle N\times M$ ($\displaystyle 2\le N, M\le 50$) tower blocks viewed from above.

The horizontal cross sections of the towers are identical squares. The number of levels of a tower block can vary between 1 and 9. On each level of each tower block there is exactly one flat. Create your program i352 to answer the following questions by using data from the file telep.txt. Before writing any result to the screen, the number of the actual task (for example, Task #3:) should be displayed. If the user is prompted to enter any data, then the type of this requested input should also be shown. Diacritical marks in the output may be omitted. The first line of the file telep.txt contains the values of $\displaystyle N$ and $\displaystyle M$; the following $\displaystyle N$ lines describe the number of levels of each tower block; and the last line of the file contains a one-letter abbreviation of the colors used to paint the tower blocks. The example Példa telep.txt fájl'' shows a sample telep.txt file: the string fszn'' abbreviates the colors fehér'' (white), sárga'' (yellow), zöld'' (green) and narancs'' (orange).

1. Read the data from the file telep.txt and solve the following tasks.

2. Determine the percentage of the flats that are located in a tower having $\displaystyle 1,2,\dots,9$ levels. You should use two decimal digits and the following format:

3. Give the number of flats with a 360-degree panorama. A flat has a 360-degree panorama, if the view is not blocked in any of the four directions (vertical or horizontal, if the tower blocks are viewed from above). Flats on the same or higher levels of other towers block the view in a given direction.

During remodeling, vertical stripes are painted on the towers in a way that consecutive levels of a tower will have the colors specified by the last line of the input file. Colors should be used in the given order and cyclically: they begin painting the tower in the top-left corner of the map, from its bottom level to the top, then proceed with the other towers in the same row of the map from left to right, and do this for each row. The color of the first level of a new tower should be the next color in the list following the color of the topmost level of the previous tower just completed.

4. You should write the colors of the topmost level of each tower to the output file felso.txt as specified by the example Példa kimeneti felso.txt fájl''.

5. It is important in the design of the area not to have neighboring towers with too similar colors. Prompt the user to enter a pair of coordinates representing the row and column coordinates of a tower relative to the top-left corner of the map (Példa bemenet'' in the example), then determine whether there is a neighboring tower whose coloring begins in the same way from its bottom level up (but ignoring the number of levels of the two towers): Van'' in the output (= Kimenet'') means there is a neighboring tower with this property, and Nincs'' means there is no such neighbor.

6. They place a roof advertisement as a new level on the top of the tower specified by the user input of the previous task. You should determine the number of flats from which this advertisement can be seen. Recall from Task 3 that flats on the same or higher levels of other towers block the view in a given direction (vertical or horizontal, if the map is viewed from above).

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

(10 pont)

solution, statistics

I. 353. The game Egyszámjáték'' (The Smallest Number Wins Game) was invented by the Hungarian mathematician and psychologist László Mérő: in this game each player submits a positive integer between 1 and 10000, and these numbers are collected. Numbers that have been submitted more than once are deleted. The smallest number among the remaining ones wins.

Example. Players submit the following numbers: 9, 6, 3, 7, 4, 6, 1, 6, 8, 1, 6, 5, 7, 9, 4, 2. We then remove duplicated elements. The remaining numbers are: 3, 8, 5. The player who submitted the smallest such number (3) wins.

Prepare a sheet to evaluate the game based on the numbers submitted by players in email, and to determine the winner. The file tippek.txt (UTF-8 encoded and downloadable from our web page) contains the data for players and the numbers they submitted. For each player we have the following data:

Tipp  The integer submitted by the player, $\displaystyle 1\le \mathsf{tipp}\le 10\;000$;

Név  The player's name (there can be more players with the same name);

If there are multiple submissions from the same email address, then only the first submission is taken into account (valid'') and the others are considered as invalid. You should use a spreadsheet application to solve the following tasks, but user-defined functions or macros cannot be used.

Open the tabulator-separated text file tippek.txt in the application according to the example. It is enough if your solution handles the data given in this file correctly. Your work should be saved as i353 in the default application file format. You should format the sheet according to the example, and give your answers in the cells adjacent to the messages in columns D:G by using expressions. Auxiliary computations can be performed in cells to the right of column H.

1. The winning number (Nyertes szám'') should appear in cell E2.

2. The name and email address of the winner (Nyertes neve'') should appear in cells E3 and G3, respectively.

In the following tasks you should determine some other values and numbers.

3. In cell E5 determine the number of valid submissions (Tippek száma'').

4. By using a function, determine in cell E6 the number that has been validly submitted the most often (Leggyakoribb tipp''). If there are multiple such numbers, give only one instance.

5. By using a function, determine in cells E7 and E9 the smallest and the largest valid numbers submitted (Legkisebb tipp'' and Legnagyobb tipp'').

6. In cells E8 and E10, respectively, display the player names (2. tippelője'') who submitted the smallest and the largest valid numbers for the second time. If there is no second submitter, the message nincs'' (= none) should appear.

7. You should format the sheet according to the example.

The spreadsheet (i353.xls, i353.ods, ...) together with a short documentation (i353.txt, i353.pdf, ...) describing the name and version number of the spreadsheet application should be submitted in a compressed file (i353.zip).

(10 pont)

solution, statistics

I. 354. Nowadays almost any piece of information you need can be found on the Internet. If something cannot be found, soon it will be available. Someone publishes a recipe to prepare a meal, and someone else publishes how to repair a device. Your task now is to create a short video (at most 5 minutes) to illustrate how to install a wireless router. Your video should show the process from turning on the router in default state to connecting an arbitrary wireless device in a secure way. You should create text captions to highlight the important facts, and apply voice narration. You may even use some background music. You can use any available recording tool or software to record your work with the router, to make screen snapshots or edit your video afterwards. You should submit a document (i354.pdf) containing the exact type of the router, the name of the hardware and software tools you used, and a link to your final video.

(10 pont)

solution, statistics

## Problems with sign 'S'

Deadline expired on October 10, 2014.

S. 91. Alice, Bob and Cecil are given $\displaystyle N$ ($\displaystyle 1\le N\le 60$) boxes of presents. The value of each box is known: the $\displaystyle i$th box is worth $\displaystyle a_i$ with $\displaystyle 1\le a_i\le 100$. They would like to distribute these presents in a fair way. A particular distribution of the presents among the three people is said to be fair, if the person getting the set of presents with the highest total value gets a set of presents having the smallest possible total value. For example, if the presents have values 2, 4, 5, 8, 9, 14, 15 and 20, then a fair distribution could be the following: Alice gets the presents with values 2, 9 and 15 (the total sum is 26); Bob gets the presents 4, 8 and 14 (with total sum 26); and Cecil gets the presents 5 and 20 (with total sum 25). Given the list of presents, your task is to determine the maximal sum of presents a person can get during a fair distribution (in other words, that maximal sum is to be minimized). Your program should read $\displaystyle N$ from the first line of the standard input, then the $\displaystyle a_i$ integers (separated by a space) from the following $\displaystyle N$ lines. The first and only line of the standard output should contain the minimal maximum value in a fair distribution. In the example, Példa bemenet'' is a sample input, while Példa kimenet'' is the corresponding output.

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. Partial points can be obtained if your program yields a solution

$\displaystyle \bullet$ for $\displaystyle a_i\le 40$, or

$\displaystyle \bullet$ for $\displaystyle N\le 10$.

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

(10 pont)

solution, statistics

\$Var(Body)