KöMaL Problems in Informatics, October 2014
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on November 10, 2014.
I. 355. A certain city has \(\displaystyle M\) metro lines and \(\displaystyle V\) tram lines. Each of these lines is an ordered set of stops, and one can travel in both directions along each line. It is possible to change from one line to the other one if they share a stop with the same name. You should answer the following questions.
\(\displaystyle a)\) Give the number of stops in the city.
\(\displaystyle b)\) Give the number of stops of the longest metro and longest tram line.
\(\displaystyle c)\) List those stops which cannot be reached by using only metro lines.
\(\displaystyle d)\) List two stops having the largest distance and also give this distance. The distance is defined as the number of stops between them by using the shortest route.
\(\displaystyle e)\) Suppose we want to get from an arbitrarily given stop to another one by changing lines as few times as possible, then what is the minimal number of changing lines? You should specify the number of changing lines, then give two stops such that it is impossible to get from one to the other by changing lines fewer times than this.
Your program should read the values of \(\displaystyle M\) and \(\displaystyle V\) (\(\displaystyle 1\le M, V\le 100\)) from the first line of he standard input. The following \(\displaystyle M\) lines then specify the metro lines: an integer at the beginning of each line describes the number of stops of that line, then the stop names are listed (each separated by a comma and a space). The next \(\displaystyle V\) lines contain an analogous description of the tram lines. Your program should write the answers to the above 5 questions in the first 5 lines of the standard output. In the example, ``Példa bemenet'' and ``Kimenet'' are a sample input and the corresponding output.
The source code (i355.pas, i355.cpp, ...) of your program without the .exe or any other auxiliary files generated by the compiler but with a brief documentation (i355.txt, i355.pdf, ...) of your solution should be submitted in a compressed file i355.zip, also specifying the name of the developer environment to use for compiling your source.
I. 356. Patients in a town can make an appointment for the working days with any of the three dentists. Dental services are offered at fixed prices. Our database contains data from 2011, and its structure is simpler than that of the official tables.
1. Create a new database fogorvos, and import the four given (tabulator-separated and UTF-8 encoded) text files paciens.txt, beavatkozas.txt, kategoria.txt and fizetendo.txt into the database by using the same names (paciens, beavatkozas, kategoria, fizetendo), then set the appropriate types and keys. The first line of each file contains the field names.
When solving the following tasks, queries should be saved by using names given in the parentheses. Make sure that your solution contains only the requested fields.
2. Make a query to determine the most expensive treatment type. (2legdragabb)
3. In 2011 certain workdays and holidays were swapped so that some Saturdays became workdays. This also affected our dentists' timetable. Make a query to give these special Saturdays. (3szombat)
4. Make a query to determine the income of each dentist in 2011. (4bevetel)
5. Make a query to determine the percentage of wisdom teeth removals relative to all wisdom teeth treatment. (5eltavolitas)
6. Make a query to determine the people whom patient ``1111'' could not meet at the dentist's office. (6nemtalalkozott)
7. Make a query to give whether the first or second premolars are treated more frequently. The query should display only the tooth name, and we assume that the answer to this question can be uniquely determined. (7kisorlo)
8. Create a query to list the patient IDs who visited the dentist's office at least 3 times during the past 3 weeks (that is, 21 days). (8harom)
9. Make a query to give the patients with two adjacent teeth treated in 2011. (9szomszedos)
The database containing your solution or the text file containing the SQL queries (fogorvos.odb, fogorvos.mdb, fogorvos.sql), together with a short documentation (i356.txt, i356.pdf) also describing the name and version number of the database application, should be submitted in a compressed file (i356.zip).
I. 357. Moiré patterns are unwanted patterns turning up on posters, digital photographs, or on images consisting of straight lines or regular structures. They are caused by interference on the repeating patterns, and they often make the work of a graphic designer harder. Moirés can also form on finely woven fabrics or on the surface of long straight hair, but they also appear on fences and grids consisting of solid vertical lines and repeated geometric units.
Create and save an animation in an SVG vector graphics file showing the formation of a simple moiré pattern. Most browsers (with the exception of Internet Explorer) are capable of displaying SVG files properly. A description of the SVG file structure and the animations can be found at http://svg.elte.hu/. We recommend using the (freely downloadable) Inkscape vector graphics editor.
You can create the figures (such as striped squares in the simplest case, point clouds or other striped shapes) appearing in your animation with the vector graphics editor. The animation should be done by editing the text of the image file.
The shapes should be overlaid on top of each other by rotating or translating them at appropriate speeds so that the moiré becomes visible. You are free to choose the playing time, the number of repetitions or other parameters.
The image file (i357.svg) together with a short analysis of the code creating the animation (i357.txt, i357.pdf, ...) should be submitted.
Problems with sign 'S'
Deadline expired on November 10, 2014.
S. 92. We are given \(\displaystyle N\) (\(\displaystyle 1\le N\le 2\;000\;000\)) not necessarily distinct integers, each between 1 and 1000000000, in a sequence. Select \(\displaystyle K\) (\(\displaystyle 1\le K\le N\), \(\displaystyle K\) being a given number) different integers from the sequence such that by deleting the selected numbers and all their copies from the sequence, the remaining sequence contains a longest connected subsequence of identical elements. Your program should read the values of \(\displaystyle N\) and \(\displaystyle K\) from the first line of the standard input, then the members of the sequence from the following line. The program should write the length of the longest possible subsequence of the above type to the first line of the standard output.
In the example, ``Példa bemenet'' is a sample input, and ``kimenet'' is the corresponding output. An explanation of the example is the following. By deleting all the 3s, the remaining sequence is 2 7 7 7 7 5 7, and here the four consecutive 7s form the longest identical subsequence. If we deleted a different number, we could not get a longer connected subsequence consisting of the same numbers in the remaining sequence.
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.
The source code (s92.pas, s92.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s92.txt, s92.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file s92.zip.
Upload your solutions above