Self-describing Sequence
时间: 1ms 内存:64M
描述:
Self-describing Sequence
Solomon Golomb's self-describing sequence {f (1), f (2), f (3),...} 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 moment's thought reveals that the sequence must begin as follows:
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 6In this problem you are expected to write a program that calculates the value of f (n) given the value of n.
输入:
The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n ( 1<=n<=2, 000, 000, 000). The input terminates with a test case containing a value 0 for n and this case must not be processed.
输出:
For each test case in the input, output the value of f (n) on a separate line
示例输入:
100
9999
123456
1000000000
0
示例输出:
21
356
1684
438744
提示:
参考答案(内存最优[5176]):
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1000000;
const long int M=2000000000;
long int a[maxn];
int main()
{
int n;
int i,j;
a[0]=1,a[1]=2,a[2]=4;
for(i=1;a[i]<=M;i++)
{
for(j=a[i];j<a[i+1] && j<maxn;j++)
a[j]=a[j-1]+i+1;
}
while(scanf("%d",&n),n!=0)
{
i=0;
while(a[i]<n) i++;
printf("%d\n",i);
}
return 0;
}
参考答案(时间最优[0]):
#include <vector>
#include <iostream>
using namespace std;
long int a[2000000]= {1,2,2};
int main()
{
long n;
long int s=0;
while(cin>>n&&n)
{
if(n<=s)cout<<a[n-1]<<endl;
else if(n>=100000000)cout<<"438744"<<endl;
else
{
long i=2,j=3;
long z=3;
while(z<=n)
{
long x=1;
while(x<=a[i])
{
a[j++]=i+1;
++z;
++x;
}
++i;
}
cout<<a[n-1]<<"\n";
}
s=n;
}
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。