杭电4148-Length of S(n)

Length of S(n)

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 767    Accepted Submission(s): 453

Problem Description A number sequence is defined as following:

S(1)=1,

S(2)=11,

S(3)=21,

S(4)=1211,

S(5)=111221,

S(6)=312211,

……

Now, we need you to calculate the length of S(n).

Input The input consists of multiple test cases. Each test case contains one integers n.

(1<=n<=30)

n=0 signal the end of input.

Output Length of S(n).

Sample Input

2
5
0
        

Sample Output

2
6
  
  
   一道坑爹题，题目看了半天也没看明白，过后来经学长点播终于搞清楚是神马意思了
  
  
   
          
/*
这题每个S(n)是描述S(n-1)值
例如：
S(1)=1;
S(2)=11;即描述S(1)有1个1=11
S(3)=21;即描述S(2)有2个1=21
S(4)=1211;即描述S(3)有1个2和1个1=1211
....
.....
.......
*/
#include<iostream>//因为题目给的测试数据不大，所以直接打表
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
const int MAX=5000;
char s[31][MAX];//我测试下,到了S(30)左右会长度差不多快到5000
using namespace std;//这里S[n][n]是模拟题目S(n)
void counnt()
{
    s[1][0]='1';
    s[2][0]='1';
    s[2][1]='1';
    s[3][0]='2';
    s[3][1]='1';
    int i,j,k,len;
    int num;
    for(i=4;i<=30;i++)
    {
        len=strlen(s[i-1]);
        num=1;
        k=0;
        for(j=1;j<len;j++)
        {
            if(s[i-1][j]==s[i-1][j-1])//如果前一个数字等于这一个数字那么+1
            {
                num+=1;
            }
            else//否则
            {
                if(num>9)
                {
                    s[i][k]=num%10+48;
                    k+=1;
                    num/=10;
                    s[i][k]=num+48;
                    k+=1;
                }
                else
                {
                    s[i][k]=num+48;
                    k+=1;
                    s[i][k]=s[i-1][j-1];
                    k+=1;
                    num=1;
                }
            }
        }
        if(num>9)
        {
            s[i][k]=num%10+48;
            k+=1;
            num/=10;
            s[i][k]=num+48;
            k+=1;
        }
        else
        {
            s[i][k]=num+48;
            k+=1;
            s[i][k]=s[i-1][j-1];
            k+=1;
        }
    }
}
int main()
{
    int n,m;
    counnt();
    while(cin>>n,n)
    {
        m=strlen(s[n]);
        cout<<m<<endl;
    }
    return 0;
}