HDU-1133 Buy the Ticketカトラン数チケット購入問題
タイトル:HDU-1133 Buy the Ticket
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1133
タイトル:
Buy the Ticket
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5746 Accepted Submission(s): 2391
Problem Description
The "Harry Potter and the Goblet of Fire"will be on show in the next few days. As a crazy fan of Harry Potter, you will go to the cinema and have the first sight, won’t you?
Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill).
Now the problem for you is to calculate the number of different ways of the queue that the buying process won't be stopped from the first person till the last person.
Note: initially the ticket-office has no money.
The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.
Input
The input file contains several test cases. Each test case is made up of two integer numbers: m and n. It is terminated by m = n = 0. Otherwise, m, n <=100.
Output
For each test case, first print the test number (counting from 1) in one line, then output the number of different ways in another line.
Sample Input
Sample Output
ええと、この問題は私は依然としてJavaでやっています.答えが長いlonglongも保存できません.C++は配列で保存するか、自分で大きなデータクラスを書くかのどちらかです.だから、Javaを選んだのは間違いありません.ACMの学生はJavaを理解していないなら簡単に理解することができます.少なくとも大きなデータクラスはこれを使うのが便利です.
テーマ分析では、n+m人が切符を買いに行き、m人が50、n人が100を取り、いくつかの手配人が並ぶ方法を聞いた.明らかに組み合わせに関する問題ですが、まず特殊な状況を判断してみましょう.m>=nの場合に限って列を作ることができます.そうしないと、お金は見つかりません.そして、n=0の場合は全部50を持っています.直接nの階乗でいいです.一般的には、n*mのマトリクスを1つ並べて答えを表すことができ、また、いくつかのキュー方法が確定してからnの乗算とmの乗算を直接乗せればよいので、n人を同じと見なすことができ、m人を同じと見なすことができる.では、一般的な場合の並び方を決めることができます.
第m+n人の並び方は第m+n人が多くなったと見なすことができ、本来はすでに(m+n-1)人がいたが、この人が50を持っていたら((m-1)+n)の上に一人が増えたと見なすことができ、この時第m+n人が一番後ろに立っていた(誰もが同じなので、実際にはすべての状況を考えていた)、同様に、この人が100を持っていたら、では、(m+(n-1))をベースに1人増えたのですが、人が同じなので(m,n-1)という種類もあるので、m+n番目の人の並び類数は(m,n-1)と(m-1,n)の和です(実際に最後に来た人が一番後ろに立たないと重複する並び数が出てくるので、ペンで押してみてください).では、プッシュ式が出てきます.メーターを打つ方法でプッシュを利用してm,n人の対応するキュー数を配列で格納することができます.
ふんふん、このやり方はもちろん私が思ったことではありません.私がこんなに頭がいいならいいです=-=です.ああ、私の心配なIQです.
対角線上の数字がカトラン数,すなわちm=nであれば行列数がカトラン数であることが分かった.
その後、階乗を求める手順は言うまでもなく、行列の種類数にmを乗じた階乗とnを乗じた階乗は、私たちが前に同じ紙幣を持っていた人を同じように見ていた影響を取り除いたので、私たちが得たのが最終的な答えです.ヒント:mとnの階乗を求めるときは0の階乗でも1を返すことに注意しましょう.そうしないと、n=0のときに計算結果が間違ってしまいます~~
やれやれ、コードをつけて~~
よく勉強して、毎日向上して、がんばって~~~
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1133
タイトル:
Buy the Ticket
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5746 Accepted Submission(s): 2391
Problem Description
The "Harry Potter and the Goblet of Fire"will be on show in the next few days. As a crazy fan of Harry Potter, you will go to the cinema and have the first sight, won’t you?
Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill).
Now the problem for you is to calculate the number of different ways of the queue that the buying process won't be stopped from the first person till the last person.
Note: initially the ticket-office has no money.
The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.
Input
The input file contains several test cases. Each test case is made up of two integer numbers: m and n. It is terminated by m = n = 0. Otherwise, m, n <=100.
Output
For each test case, first print the test number (counting from 1) in one line, then output the number of different ways in another line.
Sample Input
3 0
3 1
3 3
0 0
Sample Output
Test #1:
6
Test #2:
18
Test #3:
180
ええと、この問題は私は依然としてJavaでやっています.答えが長いlonglongも保存できません.C++は配列で保存するか、自分で大きなデータクラスを書くかのどちらかです.だから、Javaを選んだのは間違いありません.ACMの学生はJavaを理解していないなら簡単に理解することができます.少なくとも大きなデータクラスはこれを使うのが便利です.
テーマ分析では、n+m人が切符を買いに行き、m人が50、n人が100を取り、いくつかの手配人が並ぶ方法を聞いた.明らかに組み合わせに関する問題ですが、まず特殊な状況を判断してみましょう.m>=nの場合に限って列を作ることができます.そうしないと、お金は見つかりません.そして、n=0の場合は全部50を持っています.直接nの階乗でいいです.一般的には、n*mのマトリクスを1つ並べて答えを表すことができ、また、いくつかのキュー方法が確定してからnの乗算とmの乗算を直接乗せればよいので、n人を同じと見なすことができ、m人を同じと見なすことができる.では、一般的な場合の並び方を決めることができます.
第m+n人の並び方は第m+n人が多くなったと見なすことができ、本来はすでに(m+n-1)人がいたが、この人が50を持っていたら((m-1)+n)の上に一人が増えたと見なすことができ、この時第m+n人が一番後ろに立っていた(誰もが同じなので、実際にはすべての状況を考えていた)、同様に、この人が100を持っていたら、では、(m+(n-1))をベースに1人増えたのですが、人が同じなので(m,n-1)という種類もあるので、m+n番目の人の並び類数は(m,n-1)と(m-1,n)の和です(実際に最後に来た人が一番後ろに立たないと重複する並び数が出てくるので、ペンで押してみてください).では、プッシュ式が出てきます.メーターを打つ方法でプッシュを利用してm,n人の対応するキュー数を配列で格納することができます.
ふんふん、このやり方はもちろん私が思ったことではありません.私がこんなに頭がいいならいいです=-=です.ああ、私の心配なIQです.
対角線上の数字がカトラン数,すなわちm=nであれば行列数がカトラン数であることが分かった.
その後、階乗を求める手順は言うまでもなく、行列の種類数にmを乗じた階乗とnを乗じた階乗は、私たちが前に同じ紙幣を持っていた人を同じように見ていた影響を取り除いたので、私たちが得たのが最終的な答えです.ヒント:mとnの階乗を求めるときは0の階乗でも1を返すことに注意しましょう.そうしないと、n=0のときに計算結果が間違ってしまいます~~
やれやれ、コードをつけて~~
import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
BigInteger a=new BigInteger("1");
BigInteger c=new BigInteger("0");
BigInteger ans[][]=new BigInteger[105][105];
for(int i=0;i<=100;i++)
for(int j=0;j<=100;j++){
if(i<j) ans[i][j]=c;
else if(j==0) ans[i][j]=a;
else{
ans[i][j]=ans[i][j-1].add(ans[i-1][j]);
}
}
int count=0;
while(true){
int m=input.nextInt(),n=input.nextInt();
if(m==0 && n==0) break;
BigInteger e=new BigInteger("1");
BigInteger f=new BigInteger("0");
for(int i=1;i<=m;i++){
f=f.add(a);
e=e.multiply(f);
}
BigInteger g=new BigInteger("1");
BigInteger h=new BigInteger("0");
for(int i=1;i<=n;i++){
h=h.add(a);
g=g.multiply(h);
}
BigInteger b=ans[m][n].multiply(e).multiply(g);
System.out.println("Test #"+ ++count+":");
System.out.println(b);
}
}
}よく勉強して、毎日向上して、がんばって~~~