# First Bulgarian National Olympiad in Informatics

## June 1 and 2, 1985

### Problem.

Let n be a positive integer such that 3 < n < 9. Let T be the set of all points with positive integer coordinates (x,y) in the plane for which the inequality x+y < n holds. Every point (x,y) of T is associated with the last digit of |p.x^2+q.y^2+p|, where p and q are integers. Two points of T are called neighbouring, if they lie on the coordinate axes or on lines parallel to them, and there are no other points of T between them.

Write a programme that
a) inputs values of variables n, p and q;
b) prints out nicely the coordinates of points belonging to T and their associated digits, according to the above defined correspondence.
c) finds and prints out the arithmetic mean of all n-digit decimal numbers a_0a_1a_2...a_(n-1), that have digits a_0, a_1, ..., a_(n-1) satisfying the following conditions:
- every digit a_i is associated with a point of T according to the above given definition;
- for any two digits a_i and a_(i+1), i = 0, 1, 2, ..., n-2, their corresponding points t_i and t_(i+1) are neighbouring;
- a_0 is associated with (0,0);
- a_(n-1) is associated with point (x,y), such that x+y=n-1.
d) for an input value of n, your programme computes and prints out the number of points belonging to T and the number of all the n-digit numbers, defined in c).

### Problem 1.

Write a programme, that on given values of integer variable n and real variable x, computes the value of:

x
A = ------------------------------------
x
1 + -----------------------------
x
2 + -----------------------
x
3 + ----------------
.
..
..    x
(n-1) + -----
n + x

### Problem 2.

Determine the value of N which will be printed after running the following programme:

(FORTRAN)

N=0
X=-999
10  X=X+1
IF(X-4)**2.GE.49)N=N+1
IF(X.LT.999)GO TO 10
WRITE(3,20)N
20  FORMAT(I6)
STOP
END

(BASIC)

1 N=0
5 X=-999
10 X=X+1
15 IF(X-1)^2>=49 THEN N=N+1
20 IF X<999 THEN GO TO 10
25 PRINT N
30 END

### Problem 3.

Given numbers a_1, a_2, ..., a_{2n}, n>=1, satisfying inequalities: 0 < a_1 < a_2 < a_3 < ... < a_{2n-1} < a_{2n}. Write a programme, that computes the least possible sum of n products of pairs a_i a_j (i<>j), being participating exactly once all of the 2n numbers.

Example: One possible sum is a_1a_2 + a_3a_4 + a_5a_6 + ... + a_{2n-1}a+{2n}.

### Problem 4.

Running the below given programme we get a sequence of numbers: 4, 9, 18. Which were the input data?

(FORTRAN)

INTEGER X(3), A(3), S
DO 10 I=1,3
X(I)=I-1
20  FORMAT(I5)
DO 40 N=1,3
S=0
DO 30 I=1,3
30  S=S*X(N)+A(I)
40  WRITE(3,50)S
50  FORMAT(I5)
STOP
END

(BASIC)

5 DIM X%(2), A%(2)
10 FOR I=0 TO 2
15 X%(I)=I
20 INPUT A%(I)
25 NEXT I
30 FOR N=0 TO 2
35 S%=0
40 FOR I=0 TO 2
45 S%=S%*X%(N)+A%(I)
50 NEXT I
55 PRINT S%
60 NEXT N
65 END

### Problem 5.

Consider the table for bitwise addition XOR (exclusive OR):

XOR |  0  1
----------
0   |  0  1
1   |  1  0

An example:

10010101
XOR
11001011
--------
01011110

Let variables A and B have values 10011011 and 11001101, respectively. Using only operation "=" (assignment) and XOR, exchange the values of A and B without applying any other auxiliary variables.

### Problem 6.

"Find some errors" in the programme:

(FORTRAN)

5  FORMAT(3F5.2)
IF(X-Z)30,60,10
10  IF(X-Z)30,60,20
20  AMX=X
30  IF(Y-Z)50,60,40
40  AMX=Y
50  AMX=Z
60  WRITE(3,70) AXM
70  FORMAT(F6.2)
STOP
END

(BASIC)

5 INPUT X,Y,Z
10 IF X<Y GO TO 35
15 IF X=Y GO TO 55
20 IF X<Z GO TO 35
25 IF X=Z GO TO 55
30 AMX=X
35 IF Y<Z GO TO 50
40 IF Y=Z GO TO 55
45 AMX=Y
50 AMX=Z
55 PRINT AMX
60 END

Source is taken from the jury materials.

© The text is translated from Bulgarian by Emil Kelevedzhiev (keleved@math.bas.bg)