ACM组队安排

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 615 Accepted Submission(s): 257

Problem Description

  ACM亚洲区比赛结束，意味着开始备战明年的浙江省大学生程序设计竞赛了！
  杭州电子科技大学ACM集训队也准备开始组队。
  教练想把所有的n个队员组成若干支队伍，原则是每支队伍至少一人，最多三人。
  现在问题来了：如果已知集训队队员的数量n，请你帮教练计算出所有可能的组队方案有多少种。

  特别说明：
  队伍没有编号，即如果有A,B,C三人，{A}{BC}与{BC}{A}是同一种组队情况。

Input

输入包含多组测试数据(约1000组)，每组数据占一行，包含一个数字n(0<=n<=20)，表示ACM集训队的队员人数；n为0，表示输入结束。

Output

请输出n个队员所有可能的组队方案数，每组输出占一行。

Sample Input

Sample Output

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;


long long a[25];

void solve()
{
    a[1]=1;
    a[2]=2;
    a[3]=5;
    for(int i=4;i<=20;i++)
    {
        a[i]+=a[i-1];//自己组队
        a[i]+=a[i-2]*(i-1);//与前面n-1个人中的一个人组队，有n-1种方法，剩下的n-2个人进行组队，即a[i-2]种方法。
        a[i]+=a[i-3]*(i-1)*(i-2)/2;//与前面n-1个人中的n-2个人组队，有 C(n-1)2 种即 (n-1)(n-2)/2种方法，  剩下n-3人组队，即a[i-3]种方法。
    }
}

int main()
{
    long long n,t;
    solve();
    while(scanf("%lld",&n),n)
    {
        printf("%lld
",a[n]);
    }


    return 0;
}