Solutions for Round 9

Problem 1: Communication
Problem 2: Bases
Problem 3: Roots


Problem 1: Communication

 
  Idea of the algorithm:

* the connex components of the chalets are determined and each component is
  reduced to one chalet - representative - which "sees" everything the
  compound's chalets "see";
* the points which could be chosen within the best two-step solution:
          - the point which sees a maximum number of representatives is chosen
          - only one element from the chosen point is formed, and also the
            seen representatives;
* the extra-points are "eliminated" from the array of points thus:
          - beginning with the first chosen point, we check if the set of
            representatives it sees is included in the reunion of the sets
            corresponding to the other points in the vector;
          - if this set is included, we check if, by eliminating this point,
            the connexity of the complex chosen chalets+points is lost;
          - if the connexity is not lost, the point in the array is
            eliminated.
The programs have been tested using 12 test files, having the score,
respectively, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 5, 4.

The tests shall be sent as attached documents; these will be:
   INPUT  - for CABANE.IN and
   OUTPUT - for CABANE.OUT



The majority of the competitors didn't consider the fact that points might
appear in the array that are not needed. Mr. Mihai Stroe, who got the maximum
score, noticed it, but he didn't "aliminate" the extra points.

As no one of the participants managed to obtain the maximum score, we shall
quote as an example the teacher's source:
Solution (Pascal)

There were other programs that "worked" in the same manner,
although some of them "improved" their solution by painting out the
results of the example in the problem's text.
Input files: 1 2 3 4 5 6 7 8 9 10 11 12 Output files: 1 2 3 4 5 6 7 8 9 10 11 12


Because of the dimension of the tests, these will be sent as attached
documents in 2 files:
INPUT.ZIP, respectively OUTPUT.ZIP.
We wish you good luck further on !


              Teacher
                              Cleopatra  Pau
                           "C.D.Loga" - Highschool
                                Timisoara

Problem 2: Bases

The problem was very suitable for every participant, we think, and so
many of you have solved it. This is a very pleasing fact

The checking up was done in two situations, created by our fault.
The first one was when a single line was read from file BYTE.IN, with results
in a file BYTE.OUT.
The other situation was when many lines were read from BYTE.IN, with the
corresponding results in file BYTE.OUT.

Some well-made sources in Pascal and C.

The problem in
Pascal
As this is a shorter comment, we can afford to quote here 2 examples of C
programs (program1 program2) very well-made, signed by Mrs Vastiana Mot and Katya
Lilitko.

Input files: 1 Output files: 1 
                Teachers
                    Maria Nita & Adrian Nita
                "Emanuil Gojdu"- Highschool
                    Oradea

Problem 3: Roots

Theoretical Considerations:

p is a natural number (integer), having the following decomposition in
prime factors:

e1 e2 e3 ek
p = p * p * p * ... * p ,
1 2 3 k

where p , p , ..., p are prime numbers, and e , e , ... , e represent
1 2 k 1 2 k
natural numbers, the exponents at which the prime numbers appear.
If n is a natural number taken at random, then the e exponent of p in n!
is given by the formula:
j
e = min ä [n /(p * e )]
1<=i<=k j i i


Example:

n = 253
p = 108 = (2^2) * (3^3)
According to considerations:
- the exponent from 2^2 in 253! is 120
- the exponent from 3^3 in 253! is 41
- min (120,41) = 41.

The given score was, corresponding to the (13) tests:

1 1 1 1 1 1 2 2 2 2 2 2 2 = 20 points.

We remarked the very good times of the following sources:

Solution no. 1 (Pascal) Solution no. 2 (C)
Input files: 1 2 3 4 5 6 7 8 9 Output files: 1 2 3 4 5 6 7 8 9 
We took into consideration the maximum execution time 0.5/test.
So, even if for some tests you obtain correct results, please check the
time in which these results were obtained,too.

As we gave you a week's time to solve the problems and send us the results,
please roll the programs at home to avoid commonplace errors:
- the opening, for writing, of a text file with "RESET";
- calculuses which, for many of the tests, gave the error "Division by zero";
- when sending the problem, please respect the message's subject:
E6P3, not E6P2. Anyway, we correct the problems, but we receive different
messages than what we expect.

Still, we wish you good luck further on !

Maria and Adrian Nita teachers,
"Emanuil Gojdu" High School - Oradea


[The problems] [First Round] [Previous Round] [Next Round] [Current Round] [Romāna] [Go Back!]

Go Back!