大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

Problem C: Self­describing Sequence

Solomon Golomb’s 
self­describing sequence
 


 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:

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 ( ). The input terminates with a test case containing a value0 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

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>

/*
 * 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 ...
 */

const int NMAX = 1000000;

void solve()
{
    int n;
    if (scanf ("%d", &n) == EOF || 0 == n) {
        exit (0);
    }

    static int g[NMAX];
    g[0] = 0;
    g[1] = 1;

    int i = 1;
    int fi = 1;
    int k = 1;

    while (g[i - 1] < n) {
        g[i] = g[i - 1] + fi;
#ifndef ONLINE_JUDGE
        printf ("g[%d] = %d\n", i, g[i]);
#endif
        if (++i > g[k]) {
            ++fi;
            ++k;
        }
        assert (i < NMAX);
    }

    printf ("%d\n", i - 1);
}

int main (int argc, char **argv)
{
    while (true) {
        solve();
    }
    return 0;
}