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

Exercises and problems in Informatics
October 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)

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: 

InputOutput
6
10
3 300
2 175
5 540
3 310
11 15000
4 420
1030

Test data

SizeData fileResult
Tiny tiny1030
Small 1small17763
Small 2small2 
Small 3small3 
Large 1large12502635
Large 2large226272
Large 3large3 
Large 4large4 
Large 5large5 
Large 6large6 
Huge 1huge1 
Huge 2huge2 

(10 points)

Send your solutions by e-mail to: s@komal.hu

Deadline: 15 November 2004