Buy the Ticket
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4418 Accepted Submission(s): 1867
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.
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: 180n+m个人排队买票，并且满足
，票价为50元，其中n个人各手持一张50元钞票，m个人各手持一张100元钞票，除此之外大家身上没有任何其他的钱币，并且初始时候售票窗口没有钱，问有多少种排队的情况数能够让大家都买到票。
这个题目是Catalan数的变形，不考虑人与人的差异，如果m=n的话那么就是我们初始的Catalan数问题，也就是将手持50元的人看成是+1，手持100元的人看成是-1，任前k个数值的和都非负的序列数。
/*
解题思路（转）：( C(m+n, n) - C(m+n, m+1) ) * m! * n!
化简即 (m+n)! * (m-n+1) / (m+1)
推導過程如下：
m個人拿50，n個人拿100
1、如果n > m，那麼排序方法數為0
2、現在我們假設拿50的人用‘0’表示，拿100的人用‘1’表示。
如果有這麼一個序列0101101001001111。
當第K個位置出現1的個數多餘0的個數時就是一個不合法的序列了
任意一個不合法序列（m個0，n個1），都可以由另外一個序列（n-1個0和m+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)，
接下來簡化就不推了
(m+n)!*(m-n+1)/(m+1)
*/
#include<iostream>
#include<cmath>
using namespace std;
int a[500]={1};
int main(){
int i,j,n,k1,k,z,m,t;
k1=1;
while(scanf("%d%d",&m,&n))
{
if(m==0&&n==0) break;
printf("Test #%d:\n",k1++);
if (n>m)
{
printf("0\n");
continue;
}
t=m+n;//计算(m+n)!*(m-n+1)
k=2;
a[1]=m-n+1;
for(i=2;i<=t;i++)
{
for(j=1;j<k;j++)
a[j]=a[j]*i;
z=0;//进位
for(j=1;j<k;j++)
{
a[j]+=z;
z=a[j]/10;
a[j]%=10;
}
while(z)//仍有进位
{
a[k++]=z%10;
z/=10;
}
}
//除法
z=0;
for(i=k-1;i>=1;i--)
{
z=z*10+a[i];
a[i]=z/(m+1);
z=z%(m+1);
}
i=k-1;//去除前面的0
while(a[i]==0&&i>=1) i--;
for(;i>=1;i--)
printf("%d",a[i]);
printf("\n");
}
return 0;
}