# 7-th Bulgarian National Olympiad in Informatics

**February, 1991**

### Final round

A standard chess-board has 8 columns denoted by letters from A through
H and 8 rows denoted by digits from 1 through 8. The following problems
concern the chess king.

### Problem 1.

Program the following commands for moving the king:

`FORWARD` n -- to move repeatedly the king through n squares
forward.

`TORIGHT` n -- to move repeatedly the king through n squares to
the right hand direction.

`BACKWARD` n -- to move repeatedly the king through n squares backward.

`TOLEFT` n -- to move repeatedly the king through n squares to the
left hand direction.

`REACH` <position> -- to place the king on <position>
according to the rules of the chess game, i.e. at the next square in any
direction. The <position> is specified as usual by a combination
of one letter and one digit, e.g. A5, C7, etc..

### Problem 2.

Given an initial position of the king and a program for moving in the
following form

`BEGIN`

COMMAND_1;

COMMAND_2:

........

COMMAND_N;

END

where the commands are described in the previous problem, you should
output the sequence of moves, that the king will make.

**An example:**

Given initial position A1 and the following program

`BEGIN`

FORWARD 2;

TORIGHT 3;

REACH E4;

END

the sequence of moves can be look like the following one:

`A1 A2 A3 B3 C3 D3 E3 E4.`

### Problem 3.

Let us divide commands `FORWARD`, `TORIGHT`, `BACKWARD`
and `TOLEFT` into two groups. The first one consists of `FORWARD` and
`BACKWARD,` whereas the second one consists of` TORIGH `and`
TOLEFT. `Let us consider a program, that contains only commands`
FORWARD`, `TORIGHT`, `BACKWARD` and `TOLEFT.`
An allowed substitution is to replace two adjacent commands belonging to
different groups by one REACH command. After making such a substitution,
the total number of commands will decrease by 1.

Write a program, that transforms a given program by making substitutions
of the above type, so that the king will do the minimal number of moves.

Source: Obuchenieto po matematika i informatika, journal published by
Bulgarian Ministry of Education, n. 2, 1991, pp. 39-40.

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

Return to the Home
Page of Bulgarian Mathematics and Informatics Competitions.