Round 2: November 21st, 1997
Problem 1: Foldings
Problem 2: Game
Problem 3: Unlucky... Zeroes?


"I was satisfied that
I could answer right away and I did.
I said I don't know.
"
Mark Twain

Problem 1: Foldings (20 points)

Let it be a piece of paper on which the numbers are written in two rows. You must implement a folding of the paper, so that the numbers written on it be in ascending order.

Example:
           --- --- ---
        x | 2 | 5 | 4 |
           --- --- --- 
        y | 1 | 6 | 3 |
           --- --- --- 
            a   b   c   
In order to explain the way the folding occurs, we mark the columns with a, b, c, and the rows with x and y. The foldings will be:
x under y
c under b
b under a

Input Data:
The input file IMP.IN has the following structure:
      n               number of columns n<=10
      i1 i2 ... in    numbers on the first row
      j1 j2 ... jn    numbers on the second row

Output Data:
The IMP.OUT file consists of more lines, each with the following structure:
      letter under/on letter
, where letter is the letter that corresponds to a column or a row.

Execution time: 20 seconds/test on a 586/133 MHz.

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


Problem 2: Game (35 points)

The following game table is given:
          --- --- --- ---
      7  |   |   |   |   |
          --- --- --- --- 
      6  |   | o | o | o |
          --- --- --- ---
      5  |   | o | o | o |
          --- --- --- --- --- --- ---
      4  |   | o | o |   | x | x |   |
          --- --- --- --- --- --- ---
      3              | x | x | x |   |
                      --- --- --- ---
      2              | x | x | x |   |
                      --- --- --- ---
      1              |   |   |   |   |
                      --- --- --- ---
   
           A   B   C   D   E   F   G
It consists of two big squares of side n=4 with a common (small) square (D4). The table contains pieces marked with 'x' and 'o', placed symmetrically to D4. The purpose of the game is to exchange the positions occupied by the 'o' and 'x' pieces, with a minimum number of moves. A piece can be moved in a free adjoining square, or jump over an adjoining piece if it goes to a free square. For the above configuration, you can get to D4 from the following squares: D3, D2, D5, D6, C4, B4, E4, F4.
Diagonal moves are not allowed.
Given an input file, you have to exchange the position of the pieces marked with 'x' with the pieces marked with 'o' in as few moves as possible. The moves must be displayed on the screen, simulating the game, meanwhile the moves being counted.

Input Data:
The input file JOC.IN contains the positions of the pieces marked with 'x' (the pieces marked with 'o' are placed symmetrically to D4).

Example (for the given table):

The input file JOC.IN:
      D3
      D2
      E4
      E3
      E2
      F4
      F3
      F2
The moves are described below (we have no possibility to simulate the moves in the text of the problem):
      1 C4
      2 E4
      3 F4
      4 D4
      5 D3
      6 D5
      7 D6
      8 D4
      9 B4
      10 C4
      11 E4
      12 E3
      13 D3
      14 F3
      15 F4
      16 D4
      17 D3
      18 D5
      19 C5
      20 C4
      21 C6
      22 D6
      23 D4
      24 D2
      25 D3
      26 D5
      27 B5
      28 B4
      29 B6
      30 D6
      31 D4
      32 C4
      33 E4
      34 E2
      35 D2
      36 F2
      37 F4
      38 D4
      39 B4
      40 C4
      41 E4
      42 D4
      43 D2
      44 D3
      45 D5
      46 D4

Execution time: 20 seconds/test on a 586/133 MHz.

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


Problem 3: Unlucky... Zeroes? (20 points)

Let n be a positive integer number, so that 0<=n<=14.
You have to find how many final zero figures has p!=1*2*...*p, where p = (5^n - 1) div 4.

Input Data:
The file ZERO.IN has the following structure:
      n1
      n2
      ...
      nk
, each line containing a value for n.

Output Data:
The ZERO.OUT file has the following structure:
      p1 z1
      p2 z2
      ...
      pk zk
, where pk = (5^nk - 1) div 4 and zk is the number of zeroes at the end of pk!.

Example Input and Output:
      ZERO.IN
      4
      7
      9

      ZERO.OUT
      156 38
      19531 4881
      488281 122068
Execution time: 0.5 seconds/test on a 486DX2/66 MHz.

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


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