 |
Exercises and problems in Informatics |
Please read The Rules of the Problem Solving Competition.
New exercises of sign I
I. 85. Your program (i85.pas, ...) should implement a knight's tour on a 5x5 chessboard such that each square of the board is visited exactly once, then display the path, for example, by successively joining centres of the visited squares using line segments.
(10 points)
I. 86. Every square of a 5x5 chessboard should be marked either with 0 or 1 such that finally any of the 16 blocks of size 2x2 has a different pattern. a) How many such arrangements are possible? b) How many of these have the property that the leftmost and rightmost columns of the board are the same? c) How many possibilities remain if, additionally, congruence of the uppermost and lowermost rows in each board is also required? Your program (i86.pas, ...) is to count possibilities a), b), c) and print the results.
(10 points)
I. 87. Prepare a sheet in which the cell at the kth row and nth column contains the number of possibilities that casting k dice of different colours results in a sum of exactly n points. Your sheet (i87.xls) is to be submitted.
(10 points)
Send your solutions by e-mail to: i@komal.hu
New problem of sign S
S. 2. In a treasure-cave there are n treasures of different value and weight. We want to put some of these into our backpack capable of carrying w kilograms in a way that we collect the maximal possible value.
Write your program to compute this maximal value. The first and second lines of the input are n and w, respectively. Then, in the next n lines, weights and values of all the n treasures are entered. (No syntactic check is required, the input will be entered correctly.) The output of your program is a single number, the maximal value that can be carried. See example on page 427.
Send your source code, the short description of your algorithm and your results on the test data below.
Example:
|
Test data
|
(10 points)