Self-describing Sequence

code

6 年前

时间： 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 6

In 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

示例输入：

示例输出：

提示：

参考答案（内存最优[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;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。