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

# KöMaL Problems in Informatics, May 2016

Show/hide problems of signs:

## Problems with sign 'I'

Deadline expired on June 10, 2016.

I. 403. The UTF-8 encoded and space-separated text file csucsok.txt contains the name and height of the Hungarian mountain peaks with height at least 700 m, the name of the surrounding mountain range and the GPS coordinates. A mountain range can have several peaks. The data file contains at most 300 entries for peaks. For example:

Here the mountain Hangyás-bérc has two peaks in the file: the first has height 863 m, it is found in the mountain range Börzsöny, its latitude is $\displaystyle 47.9409^{\circ}$ N and its longitude is $\displaystyle 18.9366^\circ$ E.

The data file contains diacritical marks and the decimal mark is the comma. It is allowed, by using Notepad for example, to remove the diacritical marks, or to replace the comma as decimal mark with decimal point everywhere.

Create a program i403 to solve the following tasks. When displaying a result, your program should also print the task number.

1. Read the peak data from the file and display the number of peaks in the data file.

2. Prompt the user to enter the first few letters of a mountain range, then display the corresponding data for the peak(s). If there is no such mountain range, your program should issue a warning. (For example, if the user enters Hangyá'', then all peaks starting with Hangyá'' should be displayed.)

3. Prompt the user to enter the name of a mountain range, then display the name and height of its highest peak. If there is no such mountain range in the data file, your program should issue a warning.

4. List in alphabetical order all mountain ranges in the data file exactly once. Beside each range the number of its peaks with height at least 700 m should appear.

5. Prompt the user to enter the name of a peak, then determine its distance from the Gellért-hegy with coordinates $\displaystyle 47.483\,736\,2^\circ$ N and $\displaystyle 19.037\,055^\circ$ E. You can use the Haversine formula (https://en.wikipedia.org/wiki/Haversine_formula) to determine the great-circle distance of two points given their GPS coordinates. You should ignore the height difference of the peaks. The radius of the Earth is 6371 km.

6. Determine the two peaks whose distance is the largest. You should display the name of the peaks, that of the corresponding mountain ranges, and the distance itself.

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 i403.zip.

(10 pont)

solution, statistics

I. 404. Family relationships can be visualized not only by charts, but also by using database applications. One can find an example of this sort in the advanced-level problems for Matriculation Examination in February 2006. Now we are analyzing relationships in the Kiss–Nagy family with a database application. The following part of the family tree is stored in the database.

The data are stored in the tab-separated and UTF-8-enocded text file csaladtagok.txt, with the first line containing the field names.

1. Create a database i404. Import the data file into the database as csaladtagok. The appropriate data formats and the key should be set upon importing.

Now solve the following tasks. At each query below, only the requested values should appear. Your solutions should be saved by using the names in parentheses.

We remark that this database yields only a simplified family model, hence we assume that there were no divorces, remarriages, or there are no half-brothers or half-sisters among these people. During your solution it may become necessary to use multiple copies of the data table.

2. By using a query, give the number of males and females. (2ffino)

3. By using a query, list the married couples. Display each couple only once. (3hazasparok)

4. Prompt the user to enter the name of a family member. Then, by using a query, determine the father and mother name. If there are several family members with the same name, display data for all of them. (4apaanya)

5. By using a query, list the siblings. Each pair should appear only once. (5testverek)

6. By using a query, determine the maternal and paternal grandmothers of the grandchildren, according to the sample. If both grandmothers are missing from the database, the name of the grandchild should not appear either. (6nagyi)

7. By using a query, list the first cousins. Each pair should appear only once. (7unokateso)

8. Create a report to alphabetically list the family members in the database, and (if present) the name of their mother, and wife or husband. Your solution should use queries. The title and the column header text should be set according to the example. (8lista)

The database with a short documentation (containing the name and version number of the database application) should be submitted in a compressed file i404.zip.

(10 pont)

solution, statistics

I. 405. The drag-and-drop feature proves to be useful in many situations. It is included in HTML 5 and in the newest browsers as well. Create a webpage draganddrop.html to teach elementary arithmetic by using the drag-and-drop operation; you should handle the addition and subtraction of integers having at most two digits.

Upon loading the page, or after submitting a correct solution, some random positive or negative integers with at most two digits should appear together with the plus, minus and equality signs. The user first needs to create an exercise by dragging appropriate elements into the five dashed boxes in the middle of the screen. The user should be able to place a number (out of the 8 random numbers) into the $\displaystyle 1^\mathrm{st}$, $\displaystyle 3^\mathrm{rd}$ and $\displaystyle 5^\mathrm{th}$ boxes; and an arithmetic operation or the equality sign into the $\displaystyle 2^\mathrm{nd}$ and $\displaystyle 4^\mathrm{th}$ boxes. The boxes for/containing the arithmetic operations and the equality sign should be highlighted by using the same color. Your page should check the syntax of the exercise, and only the appropriate elements should be allowed to be dropped; for example, it should not happen that there are 0 or 2 equality signs.

Your page should notify the user when a proper exercise has been created. After a few seconds the unused elements should disappear, and 8 numbers should appear instead; one of them should be the solution of the equation.

The user should drag the appropriate number into the empty box. A wrong solution should be rejected. The page should acknowledge when the correct solution has been submitted, then create the next task.

You should only use HTML5, CSS or JavaScript elements. Your page should not contain (links to) existing JavaScript or other extensions.

The full source of the webpage (together with a list of the name and version number of the supported browsers) should be submitted in a compressed file i405.zip.

(10 pont)

solution, statistics

## Problems with sign 'I/S'

Deadline expired on June 10, 2016.

I/S. 9. Buddy discovers $\displaystyle N$ ($\displaystyle 1\le N\le 10$) interesting points in the plane and wants to visit them. Buddy can only move along directions parallel to the coordinate axes, and can only change directions at interesting points (Buddy can even turn back there). Buddy can keep his direction at an interesting point as well. His goal is to visit each interesting point by changing direction at each interesting point exactly once. We say that Buddy inspects an interesting point when he changes direction there. Buddy can pass through an interesting point several times, but wants to investigate it exactly once. He wants to pass through each interesting point and get back to its starting point. We are interested in the number of ways it is possible to inspect all points under these strict restrictions. A closed path and its reversal are considered as two different solutions. Two closed paths are also different if the interesting points have been inspected in a different order. Create a program to count the possible paths. Buddy can start from any point and wants to determine all possibilities.

Your program should read the value of $\displaystyle N$ from the first line of the standard input, then the integer coordinates of the interesting points ($\displaystyle -1000\le x, y\le 1000$) from the next $\displaystyle N$ lines. The first line of the standard output should contain the number of possible paths.

 Sample input (with newline characters replaced by / characters): Sample output 4 / 0 1 / 2 1 / 2 0 / 2 -5 2

Explanation. There are two paths: 1-2-4-3 and 3-4-2-1; Buddy starts from the origin in both cases.

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 is9.zip.

(10 pont)

solution, statistics

## Problems with sign 'S'

Deadline expired on June 10, 2016.

S. 108. Andrew and Brian play a certain game on a tree graph having $\displaystyle N$ ($\displaystyle 1\le N\le 100\,000$) vertices. The game consists of $\displaystyle M$ ($\displaystyle 1\le M\le 100\,000$) steps. Each step is one of the following two possibilities.

– Andrew selects two vertices of the tree, and puts one chocolate on every edge of the unique path between the vertices.

– Brian asks for the number of chocolates on a given edge.

The goal is to answer Brian's questions as quickly as possible.

Your program should read the values of $\displaystyle N$ and $\displaystyle M$ from the first line of the standard input, then the tree edges (represented by the integers $\displaystyle u$ and $\displaystyle v$) from the following $\displaystyle N-1$ lines. Then each of the following $\displaystyle M$ lines starts with either a letter P or Q, followed by a pair of integers $\displaystyle u, v$. This last pair denotes a pair of vertices. Letter P'' means that Andrew has put one chocolate on every edge of the unique path between the vertices $\displaystyle (u, v)$. Letter Q'' means that Brian has asked for the number of chocolates on the edge $\displaystyle (u, v)$. Your program should write the answer to Brian's questions in the successive lines of the standard output.

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 s108.zip.

(10 pont)

solution, statistics

\$Var(Body)