User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

48.1% (13/27)

Tags

uva

Description

有一個神秘的數列 = <1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, ...>

發現了嗎 ?

a_1 = 1, 所以值 "1" 出現了 1 次
a_2 = 2, 所以值 "2" 出現了 2 次
a_3 = 2, 所以值 "3" 出現了 2 次
a_4 = 3, 所以值 "4" 出現了 3 次

依此類推,如果 a_n = k,代表值 n 會在數列中出現 k 次,

而且這是一個非遞減數列 (所以對於任意的 1 ≦ i < j,恆有 a_i ≦ a_j )

那麼,a_n 的值是多少呢 ?

Input Format

輸入可能含有多筆測資,每筆測資一行,每一行都有一個正整數 n (n ≦ 3,790,000,000)。

當 n = 0 的時候代表輸入結束,請不要處理這筆測資。

Output Format

對於每筆測資請輸出一行,即 a_n。

Sample Input

1
2
3
4
5
6
7
8
9
0

Sample Output

1
2
2
3
3
4
4
4
5

Hints

a_3790000000 = 999571

Problem Source

原TIOJ1626 / Adapted from UVa 10049
Problem Setter: ATP, suhorng

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144