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

KöMaL Problems in Informatics, January 2014

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on February 10, 2014.


I. 337. Jenga is a popular game requiring some physical skills. The rules of the game (in Hungarian) can be found at http://tarsasoznijo.blog.hu/2009/04/14/jenga. By giving up some excitement of the original game and focusing on the logic, Jenga can also be played online at http://hu.freeonlinegames.com/game/jenga.

Unlike in the classical game, we now build a tower of n levels as a starting step. When viewing from the top, successive levels have the following alternating A or B structure (see the figure).

To investigate whether the tower collapses or not, each Jenga element is decomposed into three identical square-based prisms with each prism having unit weight (hence in this form the structural differences between different tower levels would disappear). The tower above an incomplete level can collapse, so let us consider the supporting edge where the tower elements and the missing ones meet. The tower collapses if the torque on the ``missing side'' of the supporting edge is greater than the torque on the other side. Let us illustrate and explain this in more detail by analyzing an example. In the figure showing a side view of a portion of the tower, the lowest level on the left has a missing Jenga element and the supporting edge is denoted by a small circle. In the computations, each element is replaced by a mass point located at the center of mass of the element; in the example we assume that the middle level has no missing Jenga elements. The torque on the missing side is 3 units (= weight × lever arm length = 6×0.5), while the torque on the other side is 7.5 units (the weight above the middle column is 6 units with arm length of 0.5 units, and the weight above the right column is 3 units with arm length of 1.5 units). Consequently, the tower in the example will not collapse.

Your program should determine the step in which the tower collapses by examining the sequence of movements of the Jenga elements. The first line of the input contains the number of levels. Then each of the following lines describes a movement by 3 numbers: the first number specifies the level number from which the element is taken, the second number (1, 2 or 3) specifies the position of this element within the level, and the third number (again 1, 2 or 3) gives the position of the element on the topmost level it is placed. The output should contain the critical step number in which the collapse occurs, and the reason of the collapse: either because of removing the element (``az eltávolítás miatt'') or because of placing the element on the top (``az elhelyezés miatt'').

In the example, ``Bemenet'' is input, and ``Kimenet'' is the corresponding output.

The first and second command line arguments to your program are the name of the input and output files, respectively.

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

(10 pont)

solution (in Hungarian), statistics


I. 338. The most complex event at the women's athletics program is the heptathlon. The women's heptathlon consists of the 100 m hurdles, the 200 m and the 800 m races, the high jump, the long jump, the shot put and the javelin throw. The scoring system is based on an international scoring table. To convert an athlete's performance X (measured in the appropriate units) into points (= ``pont''), one uses the following formula pont=[a.|x-b|c], where [ ] is the floor function and | | is the absolute value. The constants a, b and c have different values for each of the events and are determined by the International Association of Athletics Federations. The constants are displayed in the following table.

For example, if an athlete performs 180 cm in high jump, then she gets 978 points for this event.

The results of heptathletes at the 2012 Summer Olympics for each of the events and the data for computing their scores are available in the files versenyzo.txt, eredmeny.txt, vszam.txt and nemzet.txt. (Here ``versenyzo'' refers to the athlete names, ``eredmeny'' means ``result'', ``vszam'' is the event type, and ``nemzet'' is nationality.) The tabulator-separated and UTF-8-encoded text files contain the field names in their first lines.

1. Create a database named hetproba (= ``heptathlon''). The above data files should be imported into the database with the same names versenyzo, eredmeny, vszam and nemzet.

2. You should set the appropriate data formats and keys upon loading. You should not create new fields in the tables.

Tables:

You should answer the following tasks. Only the requested data should appear for each query, and nothing else. Your solutions should be saved by using the names in parentheses.

3. By using a query, determine who won the high jump event. The result should contain the athlete's name, her result and its physical unit. (3magas)

4. Make a query to list the name (= ``név''), result (= ``eredmény'') with the physical unit, and the computed points (= ``pontszám'') of the athletes scoring more than 1000 points in long jump, according to the example. (4tavol)

5. Some countries could send more than one athlete for the heptathlon events. List the number of athletes from each country. The list should be sorted in a decreasing order according to the number of athletes. (5nemzetdb)

6. By using a query, list the names of the athletes (sorted according to their national identifiers) who have valid results in all of the 7 events. (6teljesek)

7. By using a query, list for each event the number of athletes having valid results. (7szamonkent)

8. By using a query, give the results of the Hungarian athlete. The list should contain the event name, her results with the physical units, and her points. (8magyar)

9. Determine the final results of the heptathlon games. The list should contain the athlete's name, her country identifier and her total number of points, and should be sorted in a decreasing order according to the total number of points. (9vegeredmeny)

The database (hetproba.odb, hetproba.mdb, ...) together with a short documentation (i338.txt, i338.pdf), also describing the name and version number of the database application, should be submitted in a compressed file (i338.zip).

Downloadable files:

eredmeny.txt

nemzet.txt

versenyzo.txt

vszam.txt

(10 pont)

solution (in Hungarian), statistics


I. 339. Prolog is a functional programming language, in which facts and logical statements can be formulated. These formulae may contain concrete data and unknown quantities. For example, one can simply declare which teacher has which lesson on which day and hour: tanít(kovács,fizika,szerda,4). In this example, ``tanít'' means ``teaches'', ``kovács'' is the teacher's name, ``fizika'' is physics and ``szerda'' is Wednesday. Words beginning with a lower-case letter in a formula represent facts, while words beginning with an upper-case letter are variables or unknowns. Unknowns in the statements get values when the program is executed. Execution begins with checking the truth of a statement called the target statement. Suppose, for example, that the target statement is tanít(Ki,Mit,szerda,4). (Here ``Ki'' is ``Who'' and ``Mit'' is ``What subject''.) Then Prolog would evaluate this formula as true by replacing the unknowns by the values \text{\rm{Ki}}=\text{\rm{kov\'acs}} and \text{\rm{Mit}}
=\text{\rm{fizika}}. You can learn more about Prolog (in Hungarian) by reading the book Prologban programozni könnyű by Zsuzsanna Márkusz.

The Personal Edition of Visual Prolog is a freely downloadable Prolog environment suitable for learning the language. In its PIE project you can simply formulate your statements. You can have more information on Visual Prolog by visiting the http://www.visual-prolog.com site and reading the Fundamental Visual Prolog #1 and #2 online materials.

Lists also exist in Prolog, and the common list operations as usual in other functional languages can be performed on them. With the help of lists, more information can be put into a factual statement. The following list contains some basic data for the present exercise, showing the number of points (``5'' in the first example below; ``pont'' is ``point(s)'') a given contestant (``kiss_tamás'') was awarded for a particular problem (``problem 330'') in a KöMaL contest (``type i'' in the first example):

pont( [kiss_tamás,i,330,5], [benedek_andrea,b,4500,0], ...,[kiss_tamás,i,340,10] ).

Based on this list, answer each of the following questions by creating a Prolog formula with the given name and parameter(s).

1. How many contestants (= ``DB'') submitted (= ``beküld'') the solution of problem I. 330 - beküld_i330(DB)?

2. How many (= ``hány'') solutions with more than 0 points (= ``nemnulla'') were submitted altogether in the contest type P -hány_nemnulla(P,DB)?

3. How many points (= ``pont'') did each contestant (= V, ``versenyző'') get for problem B. 4500. - pontok_b4500(V,Pont)?

4. Who (= ``kik'') are the contestants of contest type C (the result is a list (= ``Lista'') of names with each name occurring only once) - kik_c(Lista)?

5. In which contest type (= P, ``pontverseny'') and for which task (= F, ``feladat'') did the contestants get the smallest number of points altogether, and how many points - legkevesebb(P,F,Pont)?

You should submit your Prolog source i339.pro that can be executed in the PIE system.

(10 pont)

solution (in Hungarian), statistics


Problems with sign 'S'

Deadline expired on February 10, 2014.


S. 86. There are N monkeys and a very large tree in a park. The first monkey is hanging from the tree by its tail. A monkey can connect to another one by grasping the other monkey's leg with one of its hands. In this way a monkey can hold other monkeys by connecting to them or the other monkeys can connect to it. An arbitrary number of monkeys can connect to the legs of a given one. We observe this monkey group for M seconds. In each second during the observation period, a monkey frees up a given hand, that is, it releases the leg of another monkey it was connected to. Your program should determine when a given monkey hits the ground. A monkey hits the ground, if it is no longer connected to the first monkey either in a direct or indirect way.

The first line of the standard input contains the number of the monkeys (1\le N\le
200\;000) and the duration of the observation (1\le M\le 400\;000, in seconds). Then each of the next N lines contains two numbers \elli and ri, describing that the left and right hands of the i^\mathrm{th} monkey, respectively, are connected to which monkey's leg. If any of these numbers is -1, then the actual monkey's actual hand is not connected to any monkey, and this hand does not hold any monkeys. The xj, yj pairs of integers in the next M lines of the standard input show that the yj hand (``1'' is left and ``2'' is right) of monkey xj releases the grasp in the j^\mathrm{th} second. The N lines of the standard output should contain the time instants of the monkeys falling to the ground: the i^\mathrm{th} line refers to the i^\mathrm{th} monkey, and it contains -1 if this monkey did not fall down during the observation period. In the example, two sample inputs (``Példa bemenet'') and the corresponding outputs (``Példa kimenet'') are displayed.

Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution. 9 further points can be obtained provided that your program solves any arbitrary valid input within 0.05 seconds of running time after loading the data.

Partial points can be obtained if your program yields a solution

- for N\le100;

- for N\le5000;

- for N\le 50\;000.

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

(10 pont)

solution (in Hungarian), statistics


$Var(Body)

Upload your solutions above