uva10049,

# 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 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

Miguel Revilla
2000-12-26

## Solution:

The table stores the start position for number i;
Then, table[i] = table[i-1] + f(n);
The idea is from Kaipeng Liu's Blog, and part of codes is also copied from him.

## Source Code:

//Wed Mar 30 13:32:08 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define MMAX    2000000001
using namespace std;

int table;
int size = 0;

void gen_numbers()
{
table = 1;
table = 2;
table = 4;
int i = 1;
for (; table[table[i] - 1] < MMAX; ++i)
for (int j = table[i]; j < table[i + 1]; ++j)
table[j] = table[j - 1] + i + 1;
size = table[i] - 1;
}

int main(int argc, char* argv[])
{
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
int n;
gen_numbers();
while (cin >> n && n)
{
cout << upper_bound(table, table + size, n) - table << endl;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}