UVa_10049_Self-describing_Sequence.cpp

Problem Links:

uva10049,

Problem:

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.
He reserved all the copyrights.

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[700000];
int size = 0;

void gen_numbers()
{
    table[0] = 1;
    table[1] = 2;
    table[2] = 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;
}