Round 10: Feburary 6th, 1998
Problem 1: Another Kind of Rubik
Problem 2: Encryption
Problem 3: Triangles

"The E.I.C. was like a box of chocolate - we never knew what we would get..."
Adapted after "The Teachings of Forrest Gump"

Problem 1: Another Kind of Rubik (80 points)

We have a rectangular board of the dimensions m x n (3 <= m,n <= 100), in which every element consists of a screen with liquid crystals and a rotating switch, whose turning senses are marked with + and -.
Initially, every one of the m x n screens of the board lists a positive integer. A move of one of the elements' switch results in the written change of both the values written on the screen that corresponds to that element and the change of the screens of the neighbour elements in a line and column (if the elements exist). The change consists in the adding 1 (if the switch turned in the direction marked with +), respectively -1 (when the switch rotates in the direction marked with -) to the values shown on the implied screens.

For example:
For a board like:
      5 2 1 3 8
      6 8 1 2 2
      4 6 5 2 9
the turning to + of the switch of the element in the position (2,3) leads to the board:
      5 2 2 3 8
      6 9 2 3 2
      4 6 6 2 9
and then, after turning to - the switch of the element in the position (1,4) the following board is obtained:
      5 2 1 2 7
      6 9 2 2 2
      4 6 6 2 9

Being given such a board and an integer x between [0, 99], describe the sequence of moves that should lead to a plate in which all the elements have on the screen the same value x.

Input Data:
The input file RUBIK.IN has the following structure:
m n x                 - m,n - the board dimensions, x - the final value;

a   a   .. a          - the initial configuration of the board;
 11  12     1n
a   a   .. a            (in a line, all the numbers are separated by a space)
 21  22     2n
a   a   .. a
 m1  m2     mn

Output Data:
For each set of input data, the output file RUBIK.OUT shall have the structure:
   k                     - the number of moves
   p  i  j               - (i , j ) are the coordinates of the switcher
    1  1  1                  s   s
   p  i  j                 activated during the move s;
    2  2  2                p  has one of the values "+" or "-" (1 <= s <= k);
   ........                 s
   p  i  j
    k  k  k

Example Input and Output:
      4 4 2
      2 3 2 3
      3 2 2 2
      3 3 1 3
      3 3 3 3
      + 2 3
      - 4 4
      - 1 4
      - 2 2

The problem was suggested for the training of the Computer Science students' group by a group of teachers: Adrian Atanasiu, Marinel Serban and Maria Nita.
The problem has a big score, because we have a partial solution. The checker is made, there is a theoretic algorithm to re-arrange the array and the tests are correct, but we don't have a solution in Pascal and we didn't get one so far, either. So if we have to confront a failure (i.e. no maximum scored solution), we won't be able to give you an example of a good solution.
Thank you !

Problem 2: Encryption (20 points)

At the end of the E-Mail Informatics Contest, the participants discovered a map containing an encrypted message. Each code has two parts. The first part contains the caracters of the message, the second part contains the encrypted representation of the message. The same caracter of the message may repeat several times. The sequence of the keys that codes the message is: 0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001, 0010, ...
The sequence of the keys means: 0 corresponds to the first character; 00 coresponds to the second character, and so on...

   0 coresponds with M
  00 coresponds with A
  01 coresponds with space character ' '
  10 coresponds with the second M ...
The encryption of every message, which contains only the digits 0 and 1, is realized by segments, each segment having the structure: The segments representing the code may be written on many lines, in the input file, omitting the enter.

Input Data:
The input data is read from the COD.IN file, having the structure:
  1. In the first line the encrypted text.
  2. In the next k lines the code (k unknown).
  3. The code ends with the binary digit group 000.
  4. 1, 2, 3 may repeat x times.

Output Data:
The output data is written in the COD.OUT file, on x lines the decrypted texts.

Example Input and Output:
      ECO IKUT

      EIC OK

Maria & Adrian Nita,
"Emanuil Gojdu" High School,

Problem 3: Triangles (20 points)

In the plane, we take n points with integer coordinates, n <= 1000. Three points, not situated on the same line, form a triangle.

Input Data:
The data is read from the file ARIE.IN, having the structure:
   n                     // representing the number of points existing in the
   a  b
    1  1                 // in the next n lines, the coordinates of the points
   a  b                     in the plane are given, separated by a space;
    2  2
   a  b
    n  n

Output Data:
The results are written in the file ARIE.OUT, with the following structure:
a  b  a  b  a  b        // representing the coordinates of the points forming
 i  i  j  j  k  k          a triangle with a minimum surface.

Example Input and Output:
      2 2
      4 2
      -3 -1
      -2 4

      -2 4 2 2 4 2

Maximum execution time: 10 seconds per test on a 586/133 MHz.

Maria & Adrian Nita,
"Emanuil Gojdu" High School,

[First Round] [Previous Round] [Next Round] [Last Round] [Romāna] [Go Back!]