|for Round 9|
Problem 1: Communication
Problem 2: Bases
Problem 3: Roots
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
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
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
Input files: 1 Output files: 1
Teachers Maria Nita & Adrian Nita "Emanuil Gojdu"- Highschool Oradea
p is a natural number (integer), having the following decomposition in
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:
e = min ä [n /(p * e )]
1<=i<=k j i i
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!]