KöMaL Problems in Informatics, September 2009

Problems with sign 'I' Deadline expired on October 12, 2009.

---

I. 217. A possible model for crystallization is described in this exercise. Suppose that we have N crystallization centres (denoted by black pixels) in a grid of M×M cells containing molten substance (white pixels). Each growing crystal should be coloured differently. Crystallization takes place on the surface of the segregated (coloured) crystal, and crystals grow toward their side neighbours. The growth rate of each crystal is the same: 1 layer in every time step.

The first figure shows a possible grid of crystals after 3 steps.

To ensure simultaneous crystallization, we examine all growing crystals in every step, adding a new layer on their surface, if possible. Only molten substance can crystallize, segregated parts no longer change.

You should create a simulation which randomly places N (3N15) crystallization centres on a grid of M×M cells (10M600). Crystals should have random colours, and should grow if there is still molten substance present, otherwise the simulation should stop.

The second figure shows a possible final state.

The source code and project files of your solution (without the .exe file or any other auxiliary files generated by the compiler) should be submitted in a compressed folder (i217.zip).

(10 pont)

solution (in Hungarian), statistics

---

I. 218. Besides forums and blogs, computer users often use mailing lists. Open lists forward each incoming e-mail, whereas closed lists only accept letters from members.

The following (fictitious) database contains some mailing lists, details about their traffic and membership information, managed by a mailing list server.

1. Prepare a new database levlista. The given four data tables (lista.txt, szemely.txt, tagsag.txt, log.txt) should be imported into the database with the corresponding names lista, szemely, tagsag and log as table names. The files are tabulator separated text files in UTF-8 encoding. The first lines contain the field names. When creating tables, appropriate types should be set, and fields suitable for keys should be marked. An individual identifier with name az should be added to the log table.

Tables

lista (nev, admin, zart)

nev The name of the list (text), this is the key. admin E-mail address of the list administrator (text). zart If the list is a closed one, only e-mails from members are forwarded (logical).

szemely (nev, email)

email E-mail address of the person (text), this is the key. nev Name of the person (text), optional.

tagsag (az, email, listanev, felirido, leirido)

az Identifier of the membership (number), this is the key. email E-mail address identifying the member (text). listanev Name of the list identifying the list (text). felirido Date of subscription of the member (date). From this date the server forwards mails of that person sent to the closed list. leirido Date of unsubscription of the member (date). This field is empty, if the member's subscription is active. If the list is closed and the membership has finished, the server no longer forwards those mails.

log (az, listanev, felado, ido)

az Identifier of the log file (counter), this is the key. listanev Addressee of the e-mail (i.e., name of the list) sent to the list server (text). felado Address of the sender of the mail (text). ido Date of receipt of the e-mail (date).

When solving the following tasks, queries and reports should be saved using the names in parentheses. In your solution, only the required columns should appear without any unnecessary data.

2. Make a query to display names of people with a tel.hu address in alphabetical order (2tel).

3. Make a report that displays mailing lists grouped by their administrators. Besides the e-mail address of an administrator, the number of lists managed by that person should also appear (3admin).

4. Make a query that displays for each list the number of e-mails sent to closed lists on the server in 2007 (4zart2007).

5. Make a query to display on which list e-mail traffic started last. Give the name of the list and the date of the first mail (5utolso).

6. Make a query to display those lists whose members currently can receive e-mails from the person with address a.and@suli.eu (6and).

7. Make a query to display the names of lists having more than 40 members at 0:00, January 1, 2008 (7tagszam).

8. Make a query to display all e-mails sent from the ``matek'' (math) list. E-mail address of the sender and reception date of the mail should also be displayed. The sorting criteria is the date of receipt of the mail (8matek).

The database (i218.odb, i218.mdb) should be submitted together with a short documentation (i218.txt, i218.pdf), also specifying the name and version number of the database management system used. These files should be compressed (i218.zip).

The above-mentioned four data tables: i218source.zip

(10 pont)

solution (in Hungarian), statistics

---

I. 219. On the website www.kísérletek.hu (with diacritical marks in the domain name) one can find practical physics problems and interesting experiments, together with some videos.

Create an approximately half minute video clip to make this website more popular by using excerpts from 5 experiments.

You may use the video editors Pinnacle VideoSpin or Cinelerra (freely downloadable from www.videospin.com and cinelerra.org). Cut those parts from the original clips which you find most interesting. You may use transition effects between different parts or create subtitles. Instead of the original voices, you (or another pleasant voice) may narrate the clip by summarizing the experiments and popularizing the webpage.

Your film should be submitted in Windows Media or MPEG-4 format (i219.wmv, i219.mp4) -- with decent compression settings, but with size less than 2 MB -- together with a short description (i219.txt, i219.pdf) containing titles of the original videos that were used to create your clip. Submitted files should be compressed (i219.zip).

(10 pont)

solution (in Hungarian), statistics

Problems with sign 'S' Deadline expired on October 12, 2009.

---

S. 46. Unlike most belief systems, Flagland's mythology is deeply interlaced with elements of natural sciences. They think for example that it brings misfortune if the main sail of a ship is not square-shaped, or its side length (in meters) is not a power of 2. According to this, only square-shaped sailcloths with side length of a power of 2 are sold in local harbors, and tailors only join up 4 sailcloths of the same size to produce a twice as big sail.

Create your program to calculate the minimal price of a sailcloth of required size, if prices of various available sailcloths are known.

The first line of the standard input contains three integers (separated by a space): the number of available sailcloths on the market, the side length 1A=2^a2048 of the required sailcloth, and the sewing cost 0V1000 in (linear) meters. Then each of the following N lines contains two integers: the side lengths 1B_i=2^b_iA of available sailcloths and their prices . Lines of the input are ordered monotonically first according to side lengths, then to prices.

The only line of the standard output should contain a single integer: the minimal price to make the required sailcloth. (This price consists of the cost of materials and possible sewing.) You can assume that a solution always exists.

In the figure, ``Bemenet'' is input, ``Kimenet'' is output, ``Optimális megoldás'' is the optimal solution, while ``szaggatott vonal jelöli a varrásokat'' is ``seams are denoted by dashed lines''.

The source code and project files of your solution (without the .exe file or any other auxiliary files generated by the compiler) together with a short documentation describing your solution should be submitted in a compressed folder (s46.zip).

Sample test cases: s46teszt.zip. Your solution has to give (a not neccessarily correct) answer to 5 out of 10 inputs in order to be judged.

(10 pont)

statistics