First Bulgarian National Olympiad in Informatics

June 1 and 2, 1985

First Day.

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

Second Day.

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
10  READ(1,20)A(I)
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)

    READ(1,5)X,Y,Z
 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