 |
Exercises and problems in Informatics |
Please read The Rules of the Problem Solving Competition.
New exercises of sign I
I. 97. Let us think and experiment.
We fix a natural number n. Do there exist n real numbers such that their sum equals their product? Can a program be written that yields all these n-tuples? Further, if there is a solution, can we fix some of the n numbers in advance?
Your text file (i97.txt) containing the answers and comments and your program (i97.pas) giving the answers are to be submitted. (10 points)
I. 98. We are given a square lattice of size mxn (with positive integers m and n). Square based right prisms are put onto each square. The heights of the prisms are given by an mxn matrix.
Write your program that displays this construction in perspective view together with its front and side views. In demo mode your program can specify the heights of the prisms, but in user mode the program should read these data from the input, then display the corresponding figures.
The program (i98.pas) is to be submitted. (10 points)
Remark. A continuation of this problem will appear next month.
I. 99. We are thirsty but fortunately there is a drink machine that accepts coins.
In the first few cells of the third row of an Excel sheet existing coins are listed in descending order.
Prepare a sheet so that one can enter the cost of a drink (being a natural number) into the first cell of the first row, then the number of necessary coins for that drink appears in the fourth row - just below the corresponding coin values.
However, there is a restriction, namely, one should first use up coins of the highest value, as many as possible, then this principle should be applied repeatedly to lower valued coins to make up the desired amount.
Your sheet (i99.xls) is to be submitted. (10 points)
Contestants are kindly asked to consider the following issues. Interpretation of the problems as well as devising and implementing the necessary routines (including the layout of the input and output) form integral parts of the solution unless we specify otherwise. We accept every reasonable interpretation, however, the points awarded can depend on your interpretation, for example, the restrictions you needed to impose in order to get a solution in reasonable time.
Secondly, it would be unfair if we gave extra information to contestants inquiring in emails, hence they are asked not to send us such requests in the future, we will reply to none of them.
Finally, a general remark: there is no bad problem as such - of course it may sometimes happen that the solution set is empty, or the required figure or data set does not exist. Questions of this type frequently occur in practice: their quick identification (possibly with appropriate proofs) can be highly valuable and often leads to reformulation of the problem or changing the viewpoint.
Send your solutions by e-mail to: i@komal.hu
New problem of sign S
S. 6. There are n people arriving at a stadium to watch a match. We know in advance who is hostile to whom among these people (hostility is assumed to be mutual). Our task is to divide these people into two groups: one group should take their seats on the left, while the other one on the right stand of the stadium in such a way that there should be no hostility among people in the same group. If such division is not possible, then we should find a ``proof''.
A proof should consist of a list of odd numbered people such that each of them is hostile to the previous and the next person in the list, moreover, the last person is hostile to the first one. (In fact, these people can not be divided into two according to the requirements above.)
Your program should read data from the standard input. People are numbered from 1 to n. The first row of the input is n, then two numbers will follow in each subsequent row - describing hostile pairs.
If an appropriate division is possible, then your program should display the result on the standard output containing all the numbers of those people who should take their seats on the left stand of the stadium (the 1-st person should be seated on the left). On the other hand, if a solution to the seating problem can not be found, then your program should display on the standard output the proof mentioned above, that is, numbers of those odd numbered people.
We can suppose that n is at most 65 000 and each person is hostile to at most 200 other fans. Please pay attention to the format of submission as specified by the rules of contest (for example, you should comment on the code, further, programs in Delphi and other ``exotic'' languages will be disqualified). (10 points)