Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Exercises and problems in InformaticsOctober 2004

## 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)

### 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:

 Input Output 6103 3002 1755 5403 31011 150004 420 1030

### Test data

 Size Data file Result Tiny tiny 1030 Small 1 small1 7763 Small 2 small2 Small 3 small3 Large 1 large1 2502635 Large 2 large2 26272 Large 3 large3 Large 4 large4 Large 5 large5 Large 6 large6 Huge 1 huge1 Huge 2 huge2

(10 points)