Round 9: January 30th, 1998
Problem 1: Communication
Problem 2: Bases
Problem 3: Roots


"I live in the name of the birds,
but especially in the name of flying.
I believe I have wings, but they
can't be seen. Everything for flying.
Everything,
to lean what is
on to what will be."
Nichita Stanescu (1933-1983),
Romanian poet.

Problem 1: Communication (30 points)

In a mountaineous region there are N chalets and M peaks; N <= 50 and M <= 200. From each chalet, respectively from each peak, only certain chalets and certain peaks can be seen.
For the cloudless nights, a communication system using bright signals is going to be installed, so that the message sent from a chalet can reach all the other chalets. But as between certain chalets the visibility (view) is obstructed by one or more peaks, certain permanent posts might need to be installed on some of the peaks, in order to assure the sending of the messages.
Determine the minimum number of peaks on which these "posts" need to be settled (installed).

Input Data:
The input file, CABANE.IN, has the following structure:
n m                        // representing the number of chalets,
			      respectively the number of peaks;

c     c    ... c
 1 1   1 2      1 k1       // in the next n lines the chalets visible for
c     c    ... c              every chalet are included, separated by a space;
 2 1   2 2      2 k2
...
c     c    ... c
 n 1   n 2      n kn

v     v    ... v           // in the next n lines, the peaks visible for
 1 1   1 2      1 i1          every chalet are entered;
v     v    ... v
 2 1   2 2      2 i2
.......
v     v    ... v
 n 1   n 2      n in

vf    vf    ... vf         // in the next m lines, the peaks visible for
 1 1    1 2       1 j1        every peak are entered;
vf    vf    ... vf
 2 1    2 2       2 j2
.......
vf    vf    ... vf
  m 1   m 2       m jm
If from a chalet or a peak, other chalets or peaks can't be seen, the corresponding line will be void.

Output Data:
The output file, CABANE.OUT, has the structure:
min           // the minimum number of chosen peaks;
v             // in the next min lines, the chosen peaks will be written,
 1               each one of them in a line.
v
 2
...
v
 min

Example Input and Output:
      CABANE.IN
      4 5
      2
      1


      1 2
      1 2 3
      2 3 4 5
      2 5
      2 3
      1 3
      1 2 4
      3 5
      4

      CABANE.OUT
      1
      2

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

Cleopatra Pau,
Timisoara.


Problem 2: Bases (25 points)

In the great temple of the wise BYTE, there is a misunderstanding between two apprentices. The "student" X gave a number, made up of figures from 0 to 9 and of the letters from A to Z, in a (random) base comprised between 2 and 36.
The second apprentice, Y, gave another number, made up in the same manner (conditions), telling him that it is equal with the first number. The quarrel reached the scholar's ears and, after some thinking, he decided that Y was right, even if the two numbers were in different bases.
The numbers may have 15 digits.

Input Data:
The input file BYTE.IN has the structure:
      x y             // where,in a line, we have the two numbers given by the
			 apprentices ( possibly written in different bases);

Output Data:
The output file BYTE.OUT has the structure:
      x(base1)=y(base2)    // where base1, respectively base2, represent the
			      smallest base for x, respectively y, in which
			      equality is realized (base1 can be different from
			      base2);
or
x<>y                 // if there is no base, between 2 and 36, in which
                        equality can be realized.

Example Input and Output:
      BYTE.IN
      12 5
      10 A
      123 456
      10 2

      BYTE.OUT
      12(3)=5(6)
      10(10)=A(11)
      123<>456
      10(2)=2(3)

Execution time: maximum 0.5 seconds per test on a 586/133 MHz.

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


Problem 3: Roots (20 points)

You are to extract the nth root from a number made of at the most 1000 digits. (for example, the 3rd root of 27 is 3, because 3*3*3 = 27); N <= 12.

Input Data:
The input data is read from the file RADICAL.IN, with the following structure:
   n x            // where n is the index of the root and x is the number for
		     which the root is to be extracted;

Output Data:
The output data is written in the file RADICAL.OUT, with the following structure:
y              // where y is the requested root;
                  if y is a real number, then four decimals, rounded, are
                  requested;

Examples Input and Output:
      RADICAL.IN
      3 2097152

      RADICAL.OUT
      128

      RADICAL.IN
      6 2.985984

      RADICAL.OUT
      1.2000

Maximum Execution Time: 10 seconds per test on a 586/133 MHz.

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


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