2nd Round: 22nd of January 1997

1st Problem
2nd Problem
3rd Problem
1st Problem : Knights (25 points)


We have a board of size n*n, where 3 <= n <=20, and the fields counted from 1 to n*n. In the corners there are two white knights,respectively two black knights.
Change the places of the black knights with the white ones with a minimum number of moves. The move of the knights is alternative. 

            ----------------------
            |1     |2     | 3    |
            |   o  |      |   o  |
            |      |      |      |
            ----------------------
            |4     |5     |6     |
            |      |      |      |
            |      |      |      |
            ----------------------
            |7     |8     |9     |
            |   *  |      |   *  |
            |      |      |      |
            ----------------------

In the upper drawing the white horses have been marked with "o" and the black ones with "*" . The size of the board, n, is read from the keyboard.
The result is written in the file "solution" which will contain on different columns the alternative moves of the knights, specifying at the beginning of each columns which knight is moved. The move of the knights is written n1-n2. In the last line write the number of the moves.
Example: 
n = 3
the file "solution": 
 o   *   o   *
1-6 7-2 3-8 9-4
6-7 2-9 8-1 4-3
7-2 9-4 1-6 3-8
2-9 4-3 6-7 8-1
16
Maximum time for test for a number n , 15" for 386 at 33MHz.
prof. Maria and Adrian Nita
"Emanuil Gojdu" Highschool, Oradea
2nd Problem: Triangles (25 points)

Having n (3<= n <=100) points in plane, find out three of them which make a triangle which containes the maximum number of points from the ones left.

The informations are read from the file "trdate", having the following stucture: 

n
x1 y1
x2 y2
.....
xn yn
where n is the number of points, and xi, yi the coordonates of the points.
The solution is written in the file "trsol" having the structure: 
a b
c d
e f
p
where (a,b), (c,d), (e,f) are the coordonates of the vertexes of the triangle, and p the number of points situated in the interior of the triangle. A point situated on a side of the triangle is considered being in interior.
Maximum time for test 30" for a 386 at 33MHz.

prof. Maria and Adrian Nita
"Emanuil Gojdu" Highschool, Oradea
3rd Problem: Damn this Maths! (25 points)

Having an expression : 

op nr_1 nr_2 ... nr_n = result
where:
op is one of the four elementary operations: +, -, *, /
nr_1 ... nr_n are n integers between 1 and 10.000.
op acts on all the numbers nr_i. Find the format of each number nr_i (in other words: permutating the figures that compose it), to obtain the result situated after "=".
Example: 
+ 23 17 = 49

23 may be considered in the sum as 23 or 32
17 may be considered in the sum as 17 or 71
The solution is: 
+ 32 17 = 49
The dates are read from the file "ardat" having the following structure: 
op nr_1 nr_2 ... nr_n = result
Attention! There can be more sets of dates in the file "ardat" !!! The solution will be written in a file "arsol" having the following structure: 
op  the n numbers in the right format = result
Attention! If the input file contains more sets of dates, in the file "arsol" there will be several lines, corresponding to each set.
For the upper example: 
"ardat"
+ 23 17 = 49

"arsol"
+ 32 17 = 49
In case there is no solution, print in the file the message 
There is no solution.

Maximal time for test 30" (386 - 33MHz).

prof. Maria and Adrian Nita
"Emanuil Gojdu" Highschool, Oradea
[Index] [Important Informations] [Participants] [1st Round] [3rd Round]