COCI '16 Contest 4 #4 Rekonstruiraj

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 128M

Problem types

Mirko has written down N real numbers with finite decimal notation. Next, for each number, he wrote down the arithmetic sequence that begins with 0 and its difference is the current number. For example, if the current number is x, the corresponding arithmetic sequence will be 0, x, 2x, 3x, 4x, \dots.

On another piece of paper, Mirko has written down all members of all obtained N sequences that are in the interval [A, B], sorted in ascending order, removing possible duplicates. The next day, he seems to have lost the first paper and wants to reconstruct the initial numbers based on the second piece of paper. Help him!

Input Specification

The first line of input contains a natural number K, smaller than or equal to 50, the number of different elements in Mirko's sequences in the interval [A, B].

The second line contains integers A and B (1 \le A < B \le 10^6).

Each of the following K lines contains the K described numbers, sorted in ascending order. These will be real numbers with at most 5 decimal places.

Output Specification

You must output N lines, where N is the size of Mirko's set of initial numbers, containing Mirko's (mutually distinct) initial numbers, in any order.

If multiple possible sets exist, output the one containing the smallest amount of numbers (the one with the smallest N), and if there are multiple such sets, output any.

Scoring

In test cases worth 50\% of total points, all numbers in the input will be natural.

Sample Input 1

4
1 2
1
1.4
1.5
2

Sample Output 1

0.5
0.7

Explanation for Sample Output 1

Another correct solution is 0.5, 1.4.

Sample Input 2

5
10 25
12
13.5
18
20.25
24

Sample Output 2

6.0
6.75

Comments


  • 0
    pt48583994  commented on Nov. 23, 2025, 5:02 a.m. edited

    I generated a test that only used 16 numbers for generation, but all codes I have tested (including mine, and the editorial's code) returns 17:

    50 374103 375261
    374103 374112 374127 374144 374192 374229 374235 374284 374288 374292 374308 374334 374358 374414 374418 374487 374489 374490 374524 374530 374545 374556 374601 374602 374616 374670 374736 374745 374748 374784 374816 374851 374868 374874 374916 374920 374958 374960 374967 374978 375003 375032 375082 375132 375135 375150 375200 375213 375230 375261