杭电1133 排队买票 catalan

时间：2021-01-28 16:05:11

1133

Buy the Ticket

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5511    Accepted Submission(s): 2309

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://acm.hdu.edu.cn/showproblem.php?pid=1133 
 题意：
m+n个人排队买票，并且满足m≥n，票价为50元，其中m个人各手持一张50元钞票，n个人各手持一张100元钞票，除此之外大家身上没有任何其他的钱币，并且初始时候售票窗口没有钱，问有多少种排队的情况数能够让大家都买到票。
 

这个题目是Catalan数的变形，不考虑人与人的差异，如果m=n的话那么就是我们初始的Catalan数问题，也就是将手持50元的人看成是+1，手持100元的人看成是-1，任前k个数值的和都非负的序列数。

这个题目区别就在于m>n的情况，此时我们仍然可以用原先的证明方法考虑，假设我们要的情况数是Dm+n，无法让每个人都买到的情况数是Um+n，那么就有Dm+n+Um+n=杭电1133 排队买票 catalan C(m+n, n)，此时我们求Um+n，我们假设最早买不到票的人编号是k，他手持的是100元并且售票处没有钱，那么将前k个人的钱从50元变成100元，从100元变成50元，这时候就有n-1个人手持50元，m+1个手持100元的，所以就得到，于是我们的结果就因此得到了，表达式是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);

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std ;

const int MAXN=;

int f[MAXN],a[MAXN];

int main()

{

    int i,j,t,k,n,m;

    int x;

    int c,s;

    int sign;

    k=;

    while(cin>>m>>n&&!(m==&&n==))

    {

        printf("Test #%d:\n",++k);

        memset(f,,sizeof(f));

        memset(a,,sizeof(a));

        f[]=;

        for(i=; i<=m+n; i++)

        {

            c=;

            for(j=; j<MAXN; j++)

            {

                s=f[j]*i+c;

                f[j]=s%;

                c=s/;

            }

        }

        c=;

        if(m>=n)

        {

            x=m-n+;

            for(i=; i<MAXN; i++)

            {

                s=f[i]*x+c;

                f[i]=s%;

                c=s/;

            }

            t=;

            for(j=MAXN-; j>=; j--) if(f[j]) break;

            for(i=j; i>=; i--) a[t++]=f[i];

            x=m+;

            c=;

            sign=;

            for(i=; i<t; i++)

            {

                s=((c*)+a[i])/x;

                if(s!=) sign=;

                if(sign!=) cout<<s;

                c=(c*+a[i])%x;

            }

        }

        else cout<<"";

        cout<<endl;

    }

    return ;

}

杭电1133 排队买票 catalan

 

相关文章