KöMaL Problems in Informatics, March 2014
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on April 10, 2014.
I. 343. We are given an N×N (1N50) board. Each cell of the board is either empty or has some color. When the board is in its vertical position, the colored squares try to occupy the lowest possible empty positions due to the gravitational force. Empty squares are denoted by a . character, while colored squares can be either red (denoted by P), blue (K) or green (Z). The board is surrounded by a border preventing the colored squares from falling out.
The board can be rotated left or right, or turned upside down. After the rotation or turning, the colored squares will again occupy the lowest free positions. In the example, ``indulás'' is the starting position, ``balra forgatás után'' is the state of the board after a left rotation, and ``függőleges átforgatás után'' is the resulting state after turning the board upside down.
One side of the board contains a hole. In the original position of the board, the hole is found in the column (1KN) of the bottom row. Colored squares above this hole will always fall out, that is, they are deleted from the board. The example shows a configuration with K=4.
Successive rotations or turning of the board are described by a command string consisting of characters B, J or F: they encode a left rotation, a right rotation, or turning the board upside down, respectively.
Your program i343 should simulate the effect of successive board rotations or turnings as the given command string is executed.
The first command line argument to your program is the name of the data file describing the board and the command string. The first line of the file contains the board size N (1N50) and the hole position K (1KN). The following N lines contain the initial positions of the colored and empty squares. The last line of the file gives the command string itself (1 number of characters 50).
The second command line argument to your program is the name of the output file. The first 3 lines of this file should contain the remaining number of red (``Piros''), blue (``Kek'') and green (``Zold'') squares after all rotations and turnings have been carried out. The last N lines of the output file should describe the content of each cell of the board after these movements. In the example, ``Bemenet'' is an input, while ``Kimenet'' is the corresponding output.
The source code (i343.pas, i343.cpp, ...) of your program and a brief documentation (i343.txt, i343.pdf, ...) of your solution should be submitted, also specifying the name of the developer environment to use for compiling your source.
I. 344. A spectacular and popular event during each summer in Hungary is the Formula One championship organized at the Hungaroring racetrack in Mogyoród. The present exercise is based on the data of the championship in 2013. You should open the file f1.txt in your spreadsheet (the UTF-8 encoded and tabulator-separated file can be downloaded from our web page), then save it in the default file format of your spreadsheet application. You should take into account the following instructions when solving your tasks.
- Whenever possible, use a formula, function or reference.
- Auxiliary computations can be performed to the right of column R or below line 50.
1. Determine the total race time for each pilot (who did not fail to finish the race) in hours, moreover, for each car which is not lapped (that is, completed the maximal number of laps in the race) also determine the additional time in seconds elapsed after the winner won the race.
2. You should display the average speed (in km/h) of the first 3 winners in the range B30:B32.
3. Cell B33 should contain the usual abbreviation of the country where most of the racers came from.
4. For each non-lapped car, display the distance from the finish line at the final moment of the race assuming that they were racing at their average speed.
5. Cell A37 should contain the text ``Csapatpontszámok'' (= team points). Column A in the next 11 lines should display the team names in alphabetical order by using a formula. In the corresponding adjacent cells of column B, the total number of team points should be visible, or these cells should remain empty if none of the team pilots scored any points. (You can use the fact that each team has two pilots in the race.)
6. Under the column label csapat (= team), you should create the team name. You get the team name by removing the last part of the model name that is separated by a space. For example, if the model name is Lotus E21, then the team name should be ``Lotus''.
7. Upon entering a valid final position into cell A35, the team result should appear in cell B35 according to the following example.
8. The units (h, s, km/h, m) should appear whenever a computed quantity has such physical meaning.
9. The header of the table containing the pilots' data should be formatted according to the example.
10. Create a new sheet named pepita (= chequered). Cells of this sheet should be set to be square-shaped. Upon entering two positive integers not exceeding 250 into cells A1 and B1, the legendary black-and-white chequered flag appearing at the end of a Formula One race should be displayed by using an appropriate method. This pattern should appear beginning with cell C3, and its number of columns and number of rows are determined by the values of cells A1 and B1, respectively. The rest of the cells in the sheet should remain empty: they should not contain any given or derived data.
Your spreadsheet (i344.xls, i344.ods, ...) with a short documentation (i344.txt, i344.pdf, ...) should be submitted, also containing the name and version number of the spreadsheet application used.
Some examples are found below. In the first screenshot, ``Magyar Nagydíj'' is the Hungarian Grand Prix, ``Körök száma'' is the number of laps, ``Pályahossz'' is the length of the track, ``Versenytáv'' is the total distance to be covered during the race, ``Vezető'' is pilot, ``helyezés'' is ranking, ``pontszám'' is the number of points, ``rajtszám'' is the starting position in the starting grid, ``név'' means name, ``ország'' is the country, ``csapat'' is team, while ``modell'' is the model name. In the second screenshot, ``Versenyautó'' is race car, ``motor'' is the engine type, ``Teljesített kör'' is the number of completed laps, ``Versenyidő'' is race time, ``óra'' is hours, ``perc'' is minutes, ``másodperc'' is seconds, ``ezredmásodperc'' is one-thousandths of a second, ``órában'' is the race time expressed in fractional hours, ``Lemaradás/távolság'' means the distance from the winner, and ``idő'' refers to the corresponding time behind the winner.
Downloadable file: f1.txt
I. 345. Records from the last several hundred years are found in various archives. One may ask whether we archive and how we archive the web pages constituting our digital past. One of the archives of the Internet can be found at http://web.archive.org. You should choose 5 web pages and analyze their development: monitor their evolution and their characteristic features concerning the format and content of a particular ``era''. Among the web pages you choose there should be a news portal, a television portal, the page of a sports association, a Hungarian enterprise, and the web page of your school.
You should submit your retrospection - consisting of some several thousand characters and also containing some images - in PDF form (i345.pdf).
Problems with sign 'S'
Deadline expired on April 10, 2014.
S. 88. We are given an undirected graph with N vertices (1N100000) and M (1M<N) edges. You should determine the number of ways the edges can be directed so that every vertex has at most one outward edge. You should then give the remainder on division of this number by 1000000007.
The values of N and M should be read from the first line of the standard input. Then the integers ai and bi (1ai,biN) separated by a space should be read from the following M lines. Each (ai,bi) pair represents an undirected edge in the graph between vertices ai and bi.
Since the graph is not necessarily simple, certain (ai,bi) pairs can appear more than once in the input. The first and only line of the standard output should contain the number of possibilities modulo 1000000007.
In the example, ``Példa bemenet'' is a possible input and ``Példa kimenet'' is the corresponding output.
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. Partial points can be obtained if your program yields a solution
for N200, or
The source code (s88.pas, s88.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s88.txt, s88.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file s88.zip.
Upload your solutions above