hdu 1133 Buy the Ticket
13091 ワード
Buy the Ticket
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3246 Accepted Submission(s): 1350
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
参照:http://hi.baidu.com/nicker2010/item/1641020ec6c5e01a3b53eeed
これはカトラン数の問題で、ただm!=n、ここではネット上のいくつかの導出を引用します.
m個人は50、n個人は100 1: だから
場合
n
> mでは、ソート方法の数は 0
2: 仮定すると 50の人用 ‘0’は、 100の人用 1 に表示されます.
このようなシーケンスがある場合 0101101001001111.
K番目の位置に1の個数の余分な0の個数が現れると、非合法なシーケンスになります.
仮定m=4 n=3のシーケンスは、0110100です. 明らかに合法的ではありません 少し変えてみましょう
2番目の1(この1の前はすべて合法的)の後ろのすべてのビット0を1にして、1を0にします
手に入れる 0111011 このシーケンス1の数は0より多く、 明らかに合法的ではありません しかし、今の鍵はこのシーケンスが合法かどうかを見ることではありません.
重要なのは、私たちの非合法なシーケンスと 0110100 一対一の関係になる
すなわち、いずれかの非合法なシーケンス(m個0,n個1)は、 いずれも別のシーケンス(n−1個の0とm+1個の1)から得ることができる
また、1つのシーケンスが合法的であるか、非合法であるかを知っています.
したがって、合法的なシーケンス数 = シーケンスの合計数 - 不正シーケンスの合計
シーケンス総数はm+nをこのように計算することができる 個の位置で、 選択 n 個の位置が出てきて記入する 1, だから C(m+n, n)
不正なシーケンスの数は次のとおりです. m+n 個の位置で、 選択 m+1 個の位置が出てきて記入する 1 だから C(m+n, m+1)
そして人によって違うので、全部並べる必要があります m! * n!
最後の式は次のとおりです. ( C(m+n, n) - C(m+n, m+1) ) * m! * n! 簡略化
(m+n)! * (m-n+1) / (m+1)普及:
本来p枚50元があれば、非合法なシーケンスの数は、いずれかの非合法なシーケンス(m個0,n個1)であるべきである.
いずれも別のシーケンス(n−1個の0とm+1+p個の1)から得ることができるので、m+n 個の位置で、 選択 m+1+p 個の位置
出てきて記入する 1 だから C(m+n, m+1+p) 次の化簡は押さない. 以下のコードはこの公式に従って求めて、表を打つ(表を打つなら1つの2次元の表を打つ必要があって、表の大きさの100*100、5000以上計算する必要があります)、TLEを恐れて、直接1つの1つの計算!m
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3246 Accepted Submission(s): 1350
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
参照:http://hi.baidu.com/nicker2010/item/1641020ec6c5e01a3b53eeed
これはカトラン数の問題で、ただm!=n、ここではネット上のいくつかの導出を引用します.
m個人は50、n個人は100 1: だから
場合
n
> mでは、ソート方法の数は 0
2: 仮定すると 50の人用 ‘0’は、 100の人用 1 に表示されます.
このようなシーケンスがある場合 0101101001001111.
K番目の位置に1の個数の余分な0の個数が現れると、非合法なシーケンスになります.
仮定m=4 n=3のシーケンスは、0110100です. 明らかに合法的ではありません 少し変えてみましょう
2番目の1(この1の前はすべて合法的)の後ろのすべてのビット0を1にして、1を0にします
手に入れる 0111011 このシーケンス1の数は0より多く、 明らかに合法的ではありません しかし、今の鍵はこのシーケンスが合法かどうかを見ることではありません.
重要なのは、私たちの非合法なシーケンスと 0110100 一対一の関係になる
すなわち、いずれかの非合法なシーケンス(m個0,n個1)は、 いずれも別のシーケンス(n−1個の0とm+1個の1)から得ることができる
また、1つのシーケンスが合法的であるか、非合法であるかを知っています.
したがって、合法的なシーケンス数 = シーケンスの合計数 - 不正シーケンスの合計
シーケンス総数はm+nをこのように計算することができる 個の位置で、 選択 n 個の位置が出てきて記入する 1, だから C(m+n, n)
不正なシーケンスの数は次のとおりです. m+n 個の位置で、 選択 m+1 個の位置が出てきて記入する 1 だから C(m+n, m+1)
そして人によって違うので、全部並べる必要があります m! * n!
最後の式は次のとおりです. ( C(m+n, n) - C(m+n, m+1) ) * m! * n! 簡略化
(m+n)! * (m-n+1) / (m+1)普及:
本来p枚50元があれば、非合法なシーケンスの数は、いずれかの非合法なシーケンス(m個0,n個1)であるべきである.
いずれも別のシーケンス(n−1個の0とm+1+p個の1)から得ることができるので、m+n 個の位置で、 選択 m+1+p 個の位置
出てきて記入する 1 だから C(m+n, m+1+p) 次の化簡は押さない. 以下のコードはこの公式に従って求めて、表を打つ(表を打つなら1つの2次元の表を打つ必要があって、表の大きさの100*100、5000以上計算する必要があります)、TLEを恐れて、直接1つの1つの計算!m
1 /*hdu 1133 Buy the Ticket
2
3 (n+m)!*(n-m+1) / n+1*/
4
5 #include <stdio.h>
6 #include <string.h>
7
8 #define N 400
9
10 int a[N];
11
12 void init(int n,int b,int c)
13 {
14 int i;
15 int j;
16 int k = N;
17 int t = 0;
18 int mul = 0;
19 a[0] = 1;
20 for(i = 1; i <= n; i++)
21 {
22 t = 0;
23 mul = 0;
24 for(j = 0; j < k; j++)
25 {
26 mul = a[j] * i + t;
27 t = mul /10;
28 a[j] = mul % 10;
29 }
30 }
31
32 t = 0;
33 mul = 0;
34 for(i = 0; i < k; i++)
35 {
36 mul = a[i] * b +t;
37 a[i] = mul % 10;
38 t = mul /10;
39 }
40
41 while(k--)
42 if(a[k]) break;
43 int sum = 0;
44 t = 0;
45 for(i = k; i >=0; i--)
46 {
47 sum = sum *10 + a[i];
48 a[i] = sum / c;
49 sum = sum % c;
50 }
51 }
52 int main()
53 {
54 int t = 1;
55 int n,m;
56 while(scanf("%d%d",&n,&m))
57 {
58 if(n == 0 && m == 0)
59 break;
60 printf("Test #%d:
",t++);
61 if(m > n)
62 {printf("0
");
63 continue;
64 }
65 memset(a,0,sizeof(a));
66 init(n+m,n-m+1,n+1);
67 int k = N;
68 int i;
69 while(k--)
70 if(a[k]) break;
71 for(i = k; i >= 0; i--)
72 printf("%d",a[i]);
73 printf("
");
74 }
75 return 0;
76 }