Назад
 Начало |
 Соревнования |
| 2005 |
Подразделы
| Все задачи |
Другие разделы
Дата и время
19/12/2024 20:19:26
Задачи заочного тура личного первенства
3. Self-describing Sequence
Solomon Golomb's self-describing sequence `⟨\ f(1),\ f(2),\ f(3),\ …\ ⟩` is the only non-decreasing sequence of positive integers with the property that it contains exactly `f(k)` occurrences of `k` for each `k`. A few moments thought reveals that the sequence must begin as follows:
| `n` | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| `f(n)` | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 4 | 5 | 5 | 5 | 6 |
In this problem you are expected to write a program that calculates the value of `f(n)` given the value of `n`.
Input
The input may contain multiple test cases. Each test case occupies a separate line and contains an integer `n` (`1\ ≤\ n\ ≤\ 2,000,000,000`). The input terminates with a test case containing a value 0 for `n` and this case must not be processed.
Output
For each test case in the input output the value of `f(n)` on a separate line.
Sample Input
100 9999 123456 1000000000 0
Sample Output
21 356 1684 438744
