Etapa 6: 19 februarie 1997

Problema 1
Problema 2
Problema 1: Joc 1 (40 puncte)


Having a square board with the side 2 <= n <= 6. Its surface is composed of n*n squares, counted 1, 2, ... , n*n as in the folllowing figure. Having also n*n pieces, each of them has the size of a square, marked on each side with a number. Arrange the pieces on the board so that on the common side to be placed the same number.
Example:
For n=3, the board is : 

                   -----------------------
                  |1      |2      |3      |
                  |       |       |       |
                  |       |       |       |
                  |-------|-------|-------|
                  |4      |5      |6      |
                  |       |       |       |
                  |       |       |       |
                  |-------|-------|-------|
                  |7      |8      |9      |
                  |       |       |       |
                  |       |       |       |
                   -----------------------
and the pieces: 

               -------      -------      -------
              |   3   |    |   3   |    |   5   |
              |2     3|    |3     4|    |5     4|
              |   2   |    |   3   |    |   3   |
               -------      -------      -------

               -------      -------      -------
              |   1   |    |   3   |    |   2   |
              |0     3|    |4     1|    |0     3|
              |   2   |    |   4   |    |   3   |
               -------      -------      -------

               -------      -------      -------
              |   3   |    |   4   |    |   1   |
              |3     5|    |3     3|    |3     0|
              |   3   |    |   3   |    |   5   |
               -------      -------      -------
Solution : 
                   -----------------------
                  |   1   |   4   |   1   |
                  |0     3|3     3|3     0|
                  |   2   |   3   |   5   |
                  |-------|-------|-------|
                  |   2   |   3   |   5   |
                  |0     3|3     5|5     4|
                  |   3   |   3   |   3   |
                  |-------|-------|-------|
                  |   3   |   3   |   3   |
                  |2     3|3     4|4     1|
                  |   2   |   3   |   4   |
                   -----------------------
The input file, 'dat', has the structure: 
	n                      the size of the board
	V1 N1 E1 S1            numbers written on each piece
	V2 N2 E2 S2            read in the order:
	...........            West, North, East, South
	Vi Ni Ei Si            Remark: the index i = n*n
The output file, 'rez', containes an array, its elements are the numbers of the square holded by the pieces from the file dat.
For the given example, the file 'dat' is: 
	3
	2 3 3 2
	3 3 4 3
	5 5 4 3
	0 1 3 2
	4 3 1 4
	0 2 3 3
	3 3 5 3
	3 4 3 3
	3 1 0 5
and the file 'rez' is: 
	7 8 6
	1 9 4
	5 2 3
Remarks:
- the input file 'dat' may contain several sets of dates;
- the pieces cannot be spined.
Time for test: 30"/test on a 586 at 133MHz.
prof. Maria and Adrian Nita
"Emanuil Gojdu" Highschool
Oradea
2nd Problem: Game 2 (35 points)

N sticks are arranged one on the top of the other. Write a program which determines whether it's possible to pick up all the sticks. In case of an affirmative answer, enumerate the sticks in the order in which they have been picked up; otherwise enumerate just the ones which could be removed.

Explanation:

  1. No stick can be in a vertical position.
  2. The stick can be picked up only if on the top of it there isn't any other stick.
  3. Each stick is given through the coordinates of its extremities (which are pointes in space).
  4. A solution is requested.
  5. Suppose that the dates are correct (without validation!).
  6. N < 51.
    7. Input:
    Each set of dates will be in a text file, its name will be read from the keyboard, having the following structure:
    • on the first line N, the number of the sticks;
    • on each of the following N lines will be a stick, represented by 6 numbers (real), which are the coordinates of its extremities. (x1, y1, z1), respectively (x2, y2, z2). These numbers are in the interval [-100, 100].
    Example no.1: 
    4
0  0  0  3  0  0
2  3  1  2 -1  5
6  2  0  5  0  0
0  2  0  3  2  0
    Example no.2: 
    5
0  0  0  3  0  0
0  2  0  3  2  0
5  0  0  6  2  0
2 -1  1  2  3 -1
4  0  0  4  3  1
    Output:
    For each set of dates, the result will be written in the text file 'maroc', having this format.

    For the example no.1: 

    6  2  0  5  0  0
2  3  1  2 -1  5
0  0  0  3  0  0
0  2  0  3  2  0

    For the example no.2: 

    4  0  0  4  3  1
5  0  0  6  2  0
    On the screen, for each set of dates write 'Yes' in case that all the sticks can be picked up, or 'No' contrary.

    For the example no.1:
    Yes

    For the example no.2:
    No

    Time for test: 30"/test (586 at 133MHz).

    prof. Delia Garbacea
    Brasov
    [Index] [Important Informations] [Participants] [5th Round] [7th Round]