Hangzhou electric the competition team arrangement (ACM)

ACMTeam arrangement

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

Problem Description

  ACMThe Asian competition is over,It means that preparations for next year's Zhejiang University Student Programming Contest have begun！   杭州电子科技大学ACMThe training team is also ready to start forming teams.   The coach wants to take it allnThe players form several teams,The principle is that each team has at least one person,最多三人.   现在问题来了：If the number of players in the training team is knownn,Please help the coach to figure out how many possible team formations there are.   特别说明：   Teams are not numbered,即如果有A,B,C三人,{A}{BC}与{BC}{A}It's the same team situation.

 

Input

输入包含多组测试数据(约1000组),每组数据占一行,包含一个数字n(0<=n<=20),表示ACMThe number of players in the training team;n为0,表示输入结束.

 

Output

请输出nThe number of all possible team plans for a player,每组输出占一行.

 

Sample Input

1 2 3 4 5 0

 

Sample Output

1 2 5 14 46

 思路：There was no idea at first,Did not expect it to be recursive,a[i]表示第isituation of a team

 a[i] = a[i-1] + a[i-2] * C(i-1,1) + a[i-3] * C(i-1,2);

表示第iForm your own team+从i-1Choose one and the firstiIndividual team,The rest team up+从i-1个人里面选2个和第iIndividual team,The rest team up

AC代码：

登录后复制

      
      

       
       #include <iostream>
       
       

       
       #include <cstdio>
       
       

       
       #include <cstdlib>
       
       

       
       #include <algorithm>
       
       

       
       #include <queue>
       
       

       
       #include <stack>
       
       

       
       #include <map>
       
       

       
       #include <cstring>
       
       

       
       #include <climits>
       
       

       
       #include <cmath>
       
       

       
       #include <cctype>
       
       

       
       

       
       typedef 
       
       long 
       
       long 
       
       ll;
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       

       
       ll 
       
       a[
       
       21];
       
       

       
       

       
       void 
       
       cf()
       
       
{
       
       
    
       
       int 
       
       i;
       
       
    
       
       a[
       
       0] 
       
       = 
       
       0;
       
       
    
       
       a[
       
       1] 
       
       = 
       
       1;
       
       
    
       
       a[
       
       2] 
       
       = 
       
       2;
       
       
    
       
       a[
       
       3] 
       
       = 
       
       5;
       
       
    
       
       for(
       
       i
       
       =
       
       4; 
       
       i
       
       <=
       
       20; 
       
       i
       
       ++)
       
       
    {
       
       
        
       
       a[
       
       i] 
       
       = 
       
       a[
       
       i
       
       -
       
       1] 
       
       + 
       
       a[
       
       i
       
       -
       
       2] 
       
       * (
       
       i
       
       -
       
       1) 
       
       + 
       
       a[
       
       i
       
       -
       
       3] 
       
       * (
       
       i
       
       -
       
       1) 
       
       * (
       
       i
       
       -
       
       2) 
       
       / 
       
       2;
       
       
    }
       
       
}
       
       

       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       cf();
       
       
    
       
       int 
       
       n;
       
       
    
       
       while(
       
       scanf(
       
       "%d",
       
       &
       
       n) 
       
       && 
       
       n)
       
       
    {
       
       
        
       
       printf(
       
       "%I64d\n",
       
       a[
       
       n]);
       
       
    }
       
       
    
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.
       
       
39.
       
       
40.