夏休み合宿2週目——プッシュSゲーム

S-ボードゲーム
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit 
Status
Description
ウサギのおじさんは外から旅行から帰ってきてプレゼントを持ってきて、ウサギは喜んで自分の部屋に帰って、開けてみると碁盤で、ウサギはがっかりしました.しかし、数日もしないうちに碁盤の面白さを発見しました.起点(0,0)から終点(n,n)までの最短経路数はC(2 n,n)で、今ウサギはまた対角線(ただし対角線上の格子点に触れることができる)を通り抜けなければ、このような経路数はいくらあると思いますか?ウサギは長い間考えていたが、今はウサギにこの問題を解決してもらいたいと思っています.あなたにとって難しくないでしょう.
 
Input
1個の数n(1<=n<=35)を入力する毎に、nが−1に等しいときに入力を終了する.
 
Output
各入力データ出力パス数について、具体的なフォーマットはSampleを参照してください.
 
Sample Input

      
      
      
      

       
       
       
       1
3
12
-1 
      
      
      
      

 
Sample Output

      
      
      
      

       
       
       
       1 1 2
2 3 10
3 12 416024 
      
      
      
      

ぶんせき
dp[i][i]=dp[i-1][i]
dp[i][j]=dp[i-1][j]+dp[i][j-1]
最後の答えは2*dp[n][n]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<stdio.h>
int main()
{
    int n,i,j,t=1;
    long long a[40][40];
    while(scanf("%d",&n)&&n!=-1)
    {
        for(i=0;i<=n;i++)
       a[0][i]=1;
    for(i=1;i<=n;i++)
    {
        a[i][i]=a[i-1][i];
        for(j=i+1;j<=n;j++)
        a[i][j]=a[i-1][j]+a[i][j-1];
    }
    printf("%d %d %lld
",t++,n,2*a[n][n]);
    }
    return 0;
}