hdoj 2067ウサギの碁盤
1643 ワード
うさぎの碁盤
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8385 Accepted Submission(s): 4413
Problem Description
ウサギのおじさんは外から旅行から帰ってきてプレゼントを持ってきて、ウサギは喜んで自分の部屋に帰って、開けてみると碁盤で、ウサギはがっかりしました.しかし、数日もしないうちに碁盤の面白さを発見しました.起点(0,0)から終点(n,n)までの最短経路数はC(2 n,n)で、今ウサギはまた対角線(ただし対角線上の格子点に触れることができる)を通り抜けなければ、このような経路数はいくらあると思いますか?ウサギは長い間考えていたが、今はウサギにこの問題を解決してもらいたいと思っています.あなたにとって難しくないでしょう.
Input
1個の数n(1<=n<=35)を入力する毎に、nが−1に等しいときに入力を終了する.
Output
各入力データ出力パス数について、具体的なフォーマットはSampleを参照してください.
Sample Input
Sample Output
Author
Rabbit
Source
RPG特別練習試合
カトラン数の応用、詳しく解くhttp://www.cppblog.com/MiYu/archive/2010/08/07/122573.html
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8385 Accepted Submission(s): 4413
Problem 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
Author
Rabbit
Source
RPG特別練習試合
カトラン数の応用、詳しく解くhttp://www.cppblog.com/MiYu/archive/2010/08/07/122573.html
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
__int64 map[40][40];
int i,j,k,m,n;
int t=1;
while(scanf("%d",&n),n!=-1)
{
memset(map,0,sizeof(map));
map[1][1]=1;
for(i=2;i<=n+1;i++)
for(j=1;j<=i;j++)
{
if(j==1)
map[i][j]=map[i-1][j];
else if(j==i)
map[i][j]=map[i][j-1];
else
map[i][j]=map[i-1][j]+map[i][j-1];
}
printf("%d %d %I64d
",t++,n,map[n+1][n+1]*2);
}
return 0;
}