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

KöMaL Problems in Informatics, October 2012

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on November 12, 2012.


I. 301. Many websites offer a solution for exchanging books. For a Hungarian example, see www.rukkola.hu, but to make such a site successful, a sufficient number of users is necessary. Upon registration one can mark which books are offered and required, then the site helps distributing the books.

Each line of the file csere.txt (downloadable from our webpage) contains data for the offers and requests in a chronological order. Each piece of data within a line is separated by exactly one space: the first piece is the type of the operation (``A'' for offers and ``I'' for requests), then the day of registration of this operation is stored (counted from the creation of the site and is at most 100), finally the identifiers of the book and the user follow (both numbers at most 200). The book identifier does not denote a particular copy, rather the content. The csere.txt file contains at most 2000 lines.

The first few lines of csere.txt are shown in the example.

A 1 83 1
A 1 63 3
I 1 61 11
I 2 63 8
...

Your program (i301.pas, i301.cpp, ...) should be able to solve the following tasks. First the task number should be displayed (e.g. ``Task #4''), and a message should appear before each input describing the purpose of that input (e.g. ``Please enter a book identifier:''). Hungarian diacritical marks can be omitted.

[1.] Read and store data from the file csere.txt in an appropriate format.

[2.] Display the number of requests and offers contained in the file.

[3.] Prompt the user to enter a book identifier. Then display who and when requested it first. If still nobody, then print the message ``No requests for this book yet''.

[4.] Display the identifier of the most popular book (i.e., the book requested by the largest number of people). If there is a draw, every such item should be displayed, separated by a space, further, the book identifier should be followed by the number of requests in parenthesis, for example 18 (21) 3 (21).

[5.] Sometimes it is said in connection with such websites that everybody requests for more books than they offer. Can we justify this statement? Based on the available data display those user identifiers (in one line and separated by a space) who request for at least as many books as they offer.

[6.] The website makes pairs between requests and offers: the first requester will get the first offered copy of that book. Display the book identifier of the book that has been forwarded first, together with the number of days its requester had to wait for.

[7.] Track the route of the books. Each book route should be recorded into one line of the file mozgas.txt. The first item of the line should be the identifier of the day on which the corresponding offer for the request was found, that is, the day on which the given request-offer pair was formed. The second item should be the book identifier, finally the identifier of the offerer and requester are to be displayed. These items should be separated by a tabulator within the line. The lines within the file can be put in any order.

The source code of your program (i301.pas, i301.cpp, ...) should be submitted together with a short documentation (i301.txt, i301.pdf, ...) also describing which developer environment to use for compiling.

Downloadable file: csere.txt

(10 pont)

solution (in Hungarian), statistics


I. 302. In recent years poker has become a very popular game. Now you are going to use a spreadsheet application to randomly generate a set of cards to be dealt to each player, moreover, your program will be required to name these poker hands as well.

Cards are to be generated in cells A2:A6 and the standard French deck of cards should be used. So, for example, the ace of hearts should be displayed as in the appropriate cell in red. The ranking of this hand (if it has a name) should be written in cell A1. Regarding the terminology, you may find the page http://hu.wikipedia.org/wiki/Kártyakombinációk_(póker) hands useful.

Your solution can use an arbitrary number of auxiliary cells, but your own functions and any macros should not be used.

The spreadsheet containing your solution (i302.xls, i302.ods, ...) together with the name and version number of the application and a short description of your work (i302.txt, i302.pdf, ...) should be submitted in a compressed file i302.zip.

(10 pont)

statistics


I. 303. In this task you are going to use the Imagine Logo programming environment to draw one side of a street based on a list containing its description.

First you should create the procedures ház :m, háztömb :m :hsz, zebra :m and park :m (where ``ház'' is translated as house, ``háztömb'' as block of flats and ``zebra'' is pedestrian crossing). Then by using these, you should create the procedure utca :sor :m, where ``utca'' means street, ``:m'' refers to the size, and ``:sor'' is a list describing the structure of the street.

The elements of this last list are as follows:

hx - the number of block of flats, with x being an integer between 1 and 9;
z  - pedestrian crossing;
p  - park.

Block of flats and parks are surrounded by a pavement. Colors can be chosen arbitrarily.

Your solution should only use the automatic and functional parts of the programming language. Variables should not be used, only parametrization.

The project file together with the source code (i303.imp) should be submitted.

(10 pont)

solution (in Hungarian), statistics


Problems with sign 'S'

Deadline expired on November 12, 2012.


S. 74. We are heading toward another galaxy on our nuclear-powered spaceship and the goal is to collect as much titanium as possible during the journey. Our map contains all known galaxies connected by one-way wormholes, further, it is known that if we leave a galaxy through a wormhole, we will not be able to return there.

We also know for each galaxy the amount of uranium and titanium that can be mined there upon visiting. Uranium is used as a propellant, but its storage is quite involved, therefore only a limited amount of uranium is stored on our ship. For each wormhole it is known how much uranium is needed to pass through. Fortunately we can refill our uranium supplies in any galaxy for one unit of titanium. At the beginning of our journey we have no titanium, but our uranium supplies are full.

Your program should read the map together with the number of the starting and destination galaxies from the standard input, then compute the amount of titanium we can collect during our intergalactic space journey at the maximum, and give the corresponding itinerary.

Input: The first line of the standard input contains 5 integers, separated by a space: the number of galaxies (2\le N\le 10\;000), the number of wormholes (1\le M\le 200\;000), the number of our departure and destination galaxies (galaxies are numbered from 1 to N), and the capacity of the uranium tank of our spaceship (1\le K\le 1\;000\;000).

Then each of the following N lines describes the 1st, 2nd, ..., Nth galaxy by two integers separated by a space: giving the amount of titanium and uranium that can be mined there (0\le T,U\le 1\;000\;000). Finally, each of the last M lines describes the 1st, 2nd, ..., Mth wormhole by three integers: the number of the starting and final galaxies connected by this wormhole, and the required amount of uranium (0\le W\le 1\;000\;000) to pass through the wormhole.

We make three natural assumptions: the departure and destination galaxies are different, no two wormholes connect the same two galaxies, further, for each wormhole its entry point and exit point do not coincide.

Output: In the first line of the standard output your program should display the maximal amount of titanium we can arrive at the destination galaxy with. The second line should contain the corresponding route in the following form: the first number is the number of galaxies visited during our journey (including the starting and final galaxies as well), then the numbers of the visited galaxies should follow.

If the target galaxy cannot be reached, the standard output should only contain the number -1.

In the Examples, ``Bemenet'' is input, while ``Kimenet'' is the corresponding output.

Scoring: You can obtain 2 points for a brief and proper additional documentation clearly describing your solution. The maximal 8 points for your program can be obtained only if it can solve each valid test case within the 3 seconds time limit. Partial points can be obtained if your program can solve only smaller test cases within the allotted time, or those test cases in which the amount of fuel to pass through a wormhole is always 0.

The source code of your solution (s74.pas, s74.cpp, ...) - without the .exe or any other auxiliary files generated by the compiler - should be submitted together with a short documentation (s74.txt, s74.pdf, ...) in a compressed file s74.zip, also containing a brief description of the solution and specifying the developer environment to use for compiling the source.

Based on the idea of Gábor Danner

(10 pont)

solution (in Hungarian), statistics


$Var(Body)

Upload your solutions above