754 . Self­describing Sequence

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

Solomon Golomb's self­describing sequence
<!-- MATH: $\langle f(1), f(2), f(3), \dots \rangle$ -->
WIDTH="160" HEIGHT="34" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/754-1.gif"
ALT="$\langle f(1), f(2), f(3), \dots \rangle$">
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:


\begin{displaymath}\begin{array}{c\vert cccccccccccc} \mbox{\boldmath $n$} & 1 &... ...)$} & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 4 & 5 & 5 & 5 & 6 \end{array}\end{displaymath}




In this problem you are expected to write a program that calculates the value
of f(n) given the value of n.

Input Format

The input may contain multiple test cases. Each test case occupies a separate line
and contains an integer n
(
<!-- MATH: $1 \le n \le 2,000,000,000$ -->
WIDTH="181" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/754-3.gif"
ALT="$1 \le n \le 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 Format

For each test case in the input output the value of f(n) on a separate line.

Sample Input 1


100

9999

123456

1000000000

0

Sample Output 1


21

356

1684

438744

Hints

Problem Source

Migrated from old NTUJ.

UVA 10049

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 200
Submit
Back to Top