Problem Links:
uva10049,Problem:
Problem C: Selfdescribing Sequence
Solomon Golomb's selfdescribing sequence
Problem C: Selfdescribing Sequence |


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 (
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;
}
No comments :
Post a Comment