KöMaL Problems in Informatics, December 2013
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'Deadline expired on January 10, 2014. |
I. 334. This exercise is based on the simple game Bingo played with 90 numbers and popular in the U.S. and Australia. In this version players get 3 times 5 numbers. Based on these 5-tuples, three winners are selected:
- the first winner is the player who first has a complete 5-tuple drawn (A),
- the second winner is the player who first has two complete 5-tuples drawn (B),
- the third winner is the player who first has all three complete 5-tuples drawn (C).
The first line of the file bingo.txt contains the numbers from 1 to 90 in the order they were drawn. The next few lines contain the 5-tuples for each player (altogether 15 numbers for each person) separated by a space. The three 5-tuples of a player are the numbers in this list between positions 1 to 5, 6 to 10, and 11 to 15, respectively. The file contains data for at most 100 players. The input file and a screenshot can be downloaded from our web page.
Write a program named i334 to solve the following tasks. The program should display the number of each task first (for example: ``5th task''). If your program needs user input, print the corresponding message as well (for example: ''Enter the player's number.''). You may omit diacritical marks when displaying messages.
1. Load the contents of the file and save them in a data structure with three 5-tuples for each player.
2. Display on the screen the number of players.
3. Prompt for a number and display on the screen the number of draw it was selected in.
4. Determine and display (on the screen, and separated by a space) the numbers that were not present on any player's sheet.
5. Prompt for a player's number and a draw number. Display on the screen every number of that player, with an ``!'' symbol after a number already drawn.
6. Create a function melyikutan to determine the draw number for a 5-tuple after which all 5 elements of the tuple were drawn. Variables in connection with the drawn numbers can be used as global variables.
7. Determine the winners. One player can win several times. There can be more winners in a case A/B/C, but it is sufficient to determine one of them. You should display the type of the winner (A, B or C) in each line, and the number of the winner(s).
8. Create a random draw order. The numbers should be written in the first line of the file huzas.txt, separated by commas.
The source code (i334.pas, i334.cpp, ...) together with a short documentation (i334.txt, i334.pdf, ...) - also describing which developer environment to use for compiling your source - should be submitted.
Downloadable file: bingo.txt
(10 pont)
solution (in Hungarian), statistics
I. 335. There are several popular tabletop games for every age group: the simplest version of Super Six dice game we discuss here is a relatively new game, based on pure chance.
The rules of the game are the following. First, every player gets the same number of wooden sticks. Then a starting player is selected, and players roll a die one after another in a clockwise direction. There is a little cylinder in the game with holes numbered from 1 to 6 on its top: the current player can put one of their sticks into a hole provided that the die shows that number and the hole is still empty. If that hole has already been filled earlier, the player gets the actual stick from the hole. Six is a special number in the game, because its corresponding hole is different: a stick put into hole ``6'' falls into the cylinder and stays there until the end of the game. After rolling a ``6'', the player can roll again. The winner is who first gets rid of their sticks. (The other version of Super Six as a logic game is played with two dice and different rules.)
You should simulate the above game in a spreadsheet application and save the board in the default file format of the application named as i335.
In your solution, you should take into account the following.
- Try and use formulas, functions or references, but your own functions and any macros should not be used.
- Auxiliary computations can be performed to the right of column M, but explanatory comments should be added.
The game is now played by 3 players (``Játékos'' in the example), Anna, Blanka and Csaba. Their names should be placed in cells C3:E3. The initial number of sticks (3-9 pieces) is to be put in the cells directly beneath the corresponding player's name.
Cell B2 should contain the name of the starting player (``Kezdő''). The game simulation is to be found below the 4th row. For each turn, columns G:L should contain the distribution of the empty or filled holes on the top of the cylinder, and the number of sticks in the cylinder. Empty holes are depicted by lighter cells, whereas filled holes by darker ones.
Column B should contain the random integers corresponding to the numbers on the die in each turn, while cells below A5 contain the name of the next player according to the rules. Cells C:E should have the number of sticks for each player in each turn.
The simulation of the successive turns should continue until there is a winner. Your sheet should be able to simulate the game for 100 turns. Cells in the winning position should appear as empty ones. The name of the winner should be displayed in cell E1. A warning can be issued in cell E1, in the rare case when there is no winner in the first 100 turns.
The spreadsheet (i335.xls, i335.ods, ...) together with a short documentation (i335.txt, i335.pdf, ...) also describing your solution, and the name and version number of the spreadsheet application should be submitted in a compressed file (i335.zip).
(10 pont)
solution (in Hungarian), statistics
I. 336. One can run many types of commands written in programming or script languages on the page ideone.com. As is the case with every online solution, this one also has some advantages and drawbacks. In this task you should demonstrate the advantages, drawbacks and limits of the software you discovered in connection with at most two languages you know. You should also give some usage examples. Your description should consist of approximately 5000-7000 significant characters (the code pieces you use do not count).
Your description together with some illustrations (i335.pdf), and the source code of the programs or program pieces in your description that run in this environment should be submitted in a compressed file (i335.zip).
(10 pont)
Problems with sign 'S'Deadline expired on January 10, 2014. |
S. 85. We are given a sequence of N positive integers a_{i}, with N100000 and 1a_{i}1000000000. We are looking for significant subsequences of this sequence. A subsequence is said to be significant, if
- it consists of some consecutive elements of the original sequence, and
- its central element is not less than a prescribed number C with 1C1000000000.
To get the central element of a subsequence, first sort the subsequence into non-decreasing order, then take
- either its middle element when the subsequence length is odd,
- or the not smaller element of the two middle elements when the subsequence length is even.
For example, the central element of the sequence {9,2,1,6} is 6, while the central element of the sequence {4,9,5} is 5.
Since a given sequence has in general a large number of significant subsequences, we are only interested in the number of these significant subsequences.
Your program should read the values of N and C from the first line of the standard input, then the actual elements of the sequence from the next line. Your program should write the number of significant subsequences in the first and only line of the standard output.
In the example, a sample input (``Példa bemenet'') and the corresponding output (``Példa kimenet'') are displayed. As an explanation, notice that the following subsequences are significant: {10}, {6}, {10,5}, {5,6}, {6,2}, {10,5,6} and {10,5,6,2}.
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 1 second of running time.
Partial points can be obtained if your program yields a solution for 200 or 2000.
The source code (s85.pas, s85.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s85.txt, s85.pdf, ...) - also describing which developer environment to use for compiling the source --should be submitted in a compressed file s85.zip.
(10 pont)
$Var(Body)
Upload your solutions above