专栏首页程序编程之旅HDOJ/HDU 1133 Buy the Ticket(数论~卡特兰数~大数~)

HDOJ/HDU 1133 Buy the Ticket(数论~卡特兰数~大数~)

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

题意:

就是m+n个人去买票,票价50元,m个人只带了50元一张的纸币,n个人只带了100元一张的纸币,售票员一开始手里没有钱。 问,如何让售票员在可以全部都找零的情况下,安排这些人买票的顺序~

也就是说:到100元的人买票之前,售票员手里必须要有一张50元的。

推导过程如下: m个人拿50,n个人拿1001、 如果n > m,那么排序方法数为0,这一点很容易想清楚 2、现在我们假设拿50的人用‘0’表示,拿100的人用‘1’表示。 如果有这么一个序列0101101001001111。 当第K个位置出现1的个数多于0的个数时就是一个不合法的序列了 假设m=4,n=3的一个序列是:0110100 。 也就是说任意一个不合法序列(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)

如果没看懂:可以参考我的前面一篇卡特兰数的分析: http://blog.csdn.net/qq_26525215/article/details/51453493

import java.math.BigInteger;
import java.util.Scanner;

/**
 * @author 陈浩翔
 *
 * 2016-5-19
 */
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t=0;
        while(sc.hasNext()){
            int m =sc.nextInt();
            int n =sc.nextInt();
            if(n==0&&m==0){
                return;
            }
            System.out.println("Test #"+(++t)+":");

            if(n>m){
                System.out.println(0);
                continue;
            }

            BigInteger a = new BigInteger("1");

            for(int i=2;i<=m+n;i++){
                a=a.multiply(new BigInteger(""+i));
            }
            a=a.multiply(new BigInteger(""+(m-n+1)));
            a=a.divide(new BigInteger(""+(m+1)));
            System.out.println(a);
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDUOJ---1133(卡特兰数扩展)Buy the Ticket

    Buy the Ticket Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

    Gxjun
  • python并发编程-进程理论-进程方法-守护进程-互斥锁-01

    1.空间上的复用 ​ 多个程序公用一套计算机硬件 2.时间上的复用 ​ 切换+保存状态 ​ 保存状态:保存当前的运行状态,下次接着该状态继续执行 ...

    suwanbin
  • 常用算法整理

    王磊-AI基础
  • OJ刷题-while(scanf("%d",&n)!=EOF)

            “测试输入包含若干测试实例。当N为0时,输入结束,该实例不被处理。”这句话 是最早我对OJ的印象 以前也没见过这种输入要求, 做第一道题的时候就...

    Flaneur
  • ARTS打卡第十一周

    Dubbo框架的文章还会持续更新,不过还需要深入研究下,这次放打卡的文章,历史打卡下拉到末端可看

    公众号_松华说
  • python机票价格_如何获得在线机票的最佳可能价格

    As more and more travel agents are forced to hang fresh ‘For Lease’ signs in the...

    用户7886150
  • 算法合集 | 神奇的笛卡尔树 - HDU 1506

    笛卡尔树是一个很有意思的树形结构,因为它同时满足两个性质,从key(key就是索引位置,如下图中9的key为1,3的key为2......)来看...

    ACM算法日常
  • 黑色星期五交易无序增长

    尽管零售商正在为黑色星期五准备一些未完成的优惠,但一度狂热的购物日的光芒已经减弱,因为产品折扣在假日季节开始提前出现。以前只在黑色星期五(以及在线等价物“网络星...

    甜甜圈
  • 模拟退火算法从原理到实战【基础篇】

      模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达...

    Angel_Kitty
  • 第十八课 【ERC875】Hiblock黑客马拉松门票从定制到编码实现

    【本文目标】 通过本文,可以从一个HiBlock黑客马拉松活动门票定制,转让,出售和签到为例,说明ERC875的设计初心,ERC875的标准接口分析,也给出了...

    辉哥
  • 浅析Web数据存储-Cookie、UserData、SessionStorage、WebSqlDatabase

    Cookie 它是标准的客户端浏览器状态保存方式,可能在浏览器诞生不久就有Cookie了,为什么需要Cookie 这个东东?由于HTTP协议没有状态,所以需要...

    葡萄城控件
  • 【御数之旅-2】EDW第一天:CDMP认证备考,六大主题深度研讨

    大数据文摘
  • 光刻机能进口了!全球最大制造商ASML回应,卖给中国DUV光刻机无需美国许可

    10月14日,ASML的首席财务官Roger Dassen就向中国出口光刻机的问题发表了口头声明。他说,与中芯国际等中国客户的业务往来,表示一些情况下,出口DU...

    新智元
  • 那个靠大数据抓到拉登的公司

    据说,一家名叫帕兰提尔(Palantir)的初创公司帮助美军捕杀了奥萨马·本·拉登(Osama bin Laden)。自从这个传闻开始传播以来,阿历克斯·卡普(...

    CSDN技术头条
  • 中情局“御用”数据商帕兰提尔:用数据挖掘抓到拉登

    ? 《福布斯》中文版2013年9月下 作者|Andy Greenberg 据说,一家名叫帕兰提尔(Palanti...

    CDA数据分析师
  • 那个靠大数据抓到拉登的公司

    据说,一家名叫帕兰提尔(Palantir)的初创公司帮助美军捕杀了奥萨马·本·拉登(Osama bin Laden)。自从这个传闻开始传播以来,阿历克斯·卡普(...

    华章科技
  • 服务器又一次被恶意攻击,MongoDB被删库

    前几天在自己个人的一台腾讯云服务器上安装了MongoDB,当时着急用,就用的默认配置(端口是默认端口,也没设置密码),后来就把这事抛到脑后了,也因为经常用无线网...

    DannyHoo
  • 这是在线假冒产品的季节

    2020年的假期季节即将来临,现在应该是购物的黄金时间,但这种大流行迫使许多消费者收紧钱包。除了试图避免人群躲避COVID-19之外,今年的数字假日购物者还必须...

    用户8078865
  • 原来Otto从创办到被Uber天价收购,都是卡兰尼克自导自演

    允中 李根 卧底发自 the Jam Pad 量子位 报道 | 公众号 QbitAI ? △ Uber创始人卡兰尼克和Otto创始人莱万 2016年8月,Ube...

    量子位

扫码关注云+社区

领取腾讯云代金券