TopCoder

User's AC Ratio

81.8% (18/22)

Submission's AC Ratio

43.5% (27/62)

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

1
2
3
4
5
6
7
8
9
0

Sample Output 1

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

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1