KöMaL Problems in Informatics, March 2006
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on April 18, 2006.
I. 127. A school secretary has to make all the monthly lunch tickets for the students. In every month she gets a sample ticket, then she makes photocopies of it and cuts the copies out.
She puts the tickets already completed and the sample ticket side by side so that she can photocopy them more effectively. She makes some copies this way, then cuts the tickets out of the recent sheets. Now she places these new ones and the old ones side by side again, and repeats the procedure. (We may assume that the copy machine can copy an unlimited number of tickets at one go.) However, both the copying and the cutting process take some time, being independent of the number of tickets copied or cut out.
Prepare your program to help the secretary make the required number of tickets as fast as possible. Your program asks for the following pieces of information: the required number of tickets (including the sample ticket) and the time for photocopying and cutting one sheet. Then the program should compute the minimal time for the completion of the tickets, and also, give the necessary steps encoded by the letters P (photocopying) and C (cutting-out).
The required number of tickets is at most 1000. The secretary is very economical, she makes exactly the required number of tickets and no more.
Example (messages of the computer are in italics):
Number of tickets: 64
Copying time: 1
Cutting time: 8
Total time: 30
The source code of the program (i127.pas, i127.cpp, ...) is to be submitted.
I. 128. Prepare a LaTeX document describing the main properties of the sine and cosine functions. It should contain at least three identities, and the graphs of the functions. You should also tabulate the values of the functions at 0,1,...,90 degrees to 4 digits.
The beginning of the text should contain the usual KöMaL-header (number of the problem, name, city, class, school, e-mail address). The automatic numbering feature of LaTeX for tables, formulae and figures should be used, and you should refer to these using labels.
Both the LaTeX source code (i128.tex) and its converted PDF version (i128.pdf) should be submitted.
I. 129. The tasks of system administrators of a school are stored in a database. There is an online form to report errors. These reports are then saved in the database and allocated to a sysadmin. The error report consists of an ID code, the actual date, the ID of the faulty device and a short description of the error. Only after an error has been reported is it allocated to a sysadmin. The priority of the problem is also determined then. The status of a problem first is ``reported'', after the allocation is ``processed'', finally it is labelled ``resolved''.
The database contains the following tables:
with the following structure:
errorID : integer; ID of the error, primary key
repdat : date; the report is reported at (month-day-year)
allocdat : date; the error is allocated to a sysadmin at (month-day-year)
sysadmin : integer; ID of the responsible sysadmin
soldat : date; the problem is resolved at (month-day-year)
stat : list; with values "reported", "processed" and "resolved",
status of the error
devID : integer; ID of the faulty device
errordesc : text; description of the error
prior : list; its value can be "L","M" and "H" (low, medium, high),
priority of the problem
sysadmin : integer; ID of the sysadmin, primary key
name : text; name of sysadmin
phone : text; phone number of sysadmin
devID : integer; ID of the machine, primary key
loc : integer; location of the machine, room number
type : list; with value "PC", "SERVER" or "PRINTER",
type of the device
Your task is to answer the following questions using SQL. For the first 8 questions, an SQL ``SELECT'' should be used, while an ``UPDATE'' and ``DELETE'' command for the last 2 questions.
To help you, we maintain a sample database on the KöMaL server at http://www.komal.hu/i129. You can run SQL queries, hence test the first 8 questions.
The 10 SQL commands are to be submitted in a plain text file (i129.txt).
Problems with sign 'S'
Deadline expired on April 18, 2006.
S. 16. Write a program to suggest a step in the ``3D Tic-Tac-Toe'' game in an arbitrary position. It is a game for two players. The board consists of 4×4 vertical sticks. Players place a token (pierced balls) onto the sticks in turn. The first player has light tokens, the other one has dark. Every stick can hold 4 tokens, so that there are 43=64 tokens altogether. The player who is first to set four tokens in a straight line, either horizontally, vertically or diagonally, has won. Otherwise, if all 64 tokens are set without a straight line, the game is a draw (see the figure).
The sticks are labelled as the squares on the chessboard by a1, ..., d4.
Your program reads the standard input to get the initial state of the board. Each row contains the content of 4 sticks. Tokens of the computer are denoted by O, while tokens of the opponent are denoted by X. An empty space is denoted by a -. The first row contains sticks a1, a2, a3, a4, the second row contains sticks b1, ..., b4, and so on.
Your program should write the name of the recommended stick as the next step to the standard output.
Solutions will be tested on a 2 GHz machine, the answer in a situation should be given within 10 seconds. We will make a tournament among the submitted programs, the winner receives 10 points, the second one 8, while the others get at most 7 points -- provided they come with an adequate documentation.
See the example.
The source code of the program (s16.pas, s16.cpp, ...) and its documentation is to be submitted. (10 points)
Upload your solutions above