| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 26 | 9 | 8 | 42.105% |
Elly has a very strange measuring ruler. It has length exactly L centimeters and has marks at some (but not necessarily all) positions at integer distances from the beginning. We assume the ruler has marks at its beginning (0) and end (L). The very peculiar thing about this ruler is that all distances between any two (not necessarily neighboring) marks are distinct! More formally, if the ruler has marks at positions 0 = A1 < A2 < ... < AN = L, then (for 1 ≤ i, j, k, p ≤ N and i < j) Aj - Ai = Ak - Ap if and only if j = k and i = p.
Now Elly wants to create such a ruler with N marks, requiring it to be as short as possible. Write a program to help her.
On a single line of the standard input will be given one integer N – the number of marks (including the beginning and end), which the ruler should have.
On a single line of the standard output print N non-negative integers, ordered in increasing order – the positions of the marks of the ruler. The frst position must be 0 and the last must be L, where L is the least possible length, allowing such a ruler with N marks. If more than one solution exists, you can print any of them.
5
0 2 7 8 11
The minimal length of a ruler with the described properties with 5 marks is 11. With the given choice of mark positions, all distances between pairs of marks are: {2, 7, 8, 11, 5, 6, 9, 1, 4, 3}.
Another possible solution for N = 5 would be {0, 1, 4, 9, 11}.
8
0 1 4 9 15 22 32 34