» 今年的微软编程之美全国挑战赛的初赛题目, 展现微民网实力的时候到了!
    时间限制: 1000ms 内存限制: 256MB
    
    ===描述===
    Alice和Bob都要向同一个商人购买钻石。商人手中有 N 颗钻石，他会将它们一颗颗地卖给他们，Alice和Bob通过竞价的方式来决定钻石的归属。具体的过程如下：商人首先指定其中一个人开始报价，之后两人轮流报价，要求是一定要比对方报的价格更高。任何时候，如果一个人不愿出价或者出不起价钱时，可以宣布弃权，则对手以最后一次报的价格将钻石买下。首次报价至少为 1，并且只能报整数的价钱。
    
    Alice和Bob特别爱攀比，因此他们都希望能比对方买到更多的钻石。Alice和Bob各自带了 CA 和 CB 的钱用于竞拍钻石。此外，Alice和商人有很不错的私人关系，因此商人总是会让Alice先报价。
    现在请问，在Alice和Bob都用最优策略的情况下，谁能买到更多钻石？设:双方都知道对方手中的现金数量，以及商人将要拍卖的钻石数量(N)。
    
    
    最后编写一个程序,或者提出程序的算法
    
    ===输入===
    输入文件包含多组测试数据。
    
    第一行，给出一个整数T，为数据的组数。
    例如输入了:
    3个钻石 Alice 有10快 Bob 有20块
    那么 整数T 就是1
    如果输入了:
    3个钻石 Alice 有10快 Bob 有20块
    4个钻石 Alice 有12快 Bob 有14块
    那么 整数T 就是2
    
    
    接下来依次给出每组测试数据。
    
    每组数据为三个用空格隔开的整数 N，A，B，N表示钻石的数量，A代表Alice手里的钱数, B代表bob手里的钱数。
    
    ===输出===
    对于每组测试数据，输出一行"Case #X: Y"，
    其中X表示测试数据编号，Y的取值为{-1, 0, 1}，-1表示Alice买到的钻石会比Bob少，0表示两人能买到一样多，1表示Alice能买到更多钻石。所有数据按读入顺序从1开始编号。
    
    数据范围
    1 ≤ T ≤ 1000
    
    小数据：0 ≤ N ≤ 10; 0 < CA, CB ≤ 10
    
    大数据：0 ≤ N ≤ 105; 0 < CA, CB ≤ 106
    
    
    
    样例输入
    总共2行
    第一行 总共有4颗钻石 A持有3块钱 B持有5块钱
    第二行 总共有7颗钻石 A持有4块钱 B持有7块钱
    样例输出
    Case #1: 0
    Case #2: 1
    

网友评论2013-05-20 10:44

    看不懂...坐等高手解答...
    

网友评论2013-05-20 10:47

    递归么。。。
    

网友评论2013-05-20 10:47

    ACM。。。跪了
    

网友评论2013-05-20 10:54

    完全..没看懂
    

网友评论2013-05-20 10:57

    其实还行 分析没那么困难 搜索下能找到的
    

网友评论2013-05-20 11:00

    Reply Post by h11y11 (2013-05-20 10:57):
    
    其实还行 分析没那么困难 搜索下能找到的
    
    
    应该不会很简单
    这是今年4月的题 答案还没放出来
    做出来的人到不少 如果不看答案自己写 那真是要作死啊
    预赛3到题
    我朋友做对了第一道的小数据
    第二道就是这个
    貌似做对的不多没几个人
    我朋友就做对了一道题的小数据 就进复赛了
    

网友评论2013-05-20 11:02

    Reply to Reply Post by lingzerg (2013-05-20 11:00)
    
    这个比赛感觉知道的不多
    好多认识的没参与
    这题我研究过了
    主要容易想错的一点是不能整除的情况
    

网友评论2013-05-20 11:05

    策略最优... 猜测就是每次叫价都叫到 对方的金钱数/剩余钻石数 的数值当然钱多的一方获得钻石..
    
    然后进入下一轮 重置N 以及两个人的金钱数..
    
    目测递归可破.... 不过还有没有其他策略俺就不知道了...
    

网友评论2013-05-20 11:06

    跪舔acmer
    

网友评论2013-05-20 11:08

    
    

网友评论2013-05-20 11:11

    从CA与CB的差值入手，感觉上
    当abs(CA-CB)>=N时，结果很明显
    其他情况要好好想一下...
    
    总觉得玩报价的人会吃亏...
    

网友评论2013-05-20 11:12

     数学没学好。。。。题目都看不懂
    

网友评论2013-05-20 11:12

    对于一个只会IF ELSE IF的编程文盲来说，
    
    算了，我还是帮顶一下，顺便看看有木有高人能给出一些逻辑上的提示。
    

网友评论2013-05-20 11:14

    Reply Post by h11y11 (2013-05-20 11:02):
    
    这个比赛感觉知道的不多
    好多认识的没参与
    这题我研究过了
    主要容易想错的一点是不能整除的情况
    
    反正我是给跪了...
    2个小时毛都没想出来
    真是跪添ACMER...
    

网友评论2013-05-20 11:15

    微软这东西应该来说不会太简单
    

网友评论2013-05-20 11:15

    主要在研究abs(cb-ca)《n的这段么？
    

网友评论2013-05-20 11:15

    Reply to Reply Post by lingzerg (2013-05-20 11:14)
    
    感觉这个比赛真不火 知道的人太少
    大腾讯马拉松赛碾压这个
    我记得有一天被碾压的渣渣都不剩
    

网友评论2013-05-20 11:17

    我看成全美编程挑战赛了
    

网友评论2013-05-20 11:25

    A 0块钱，B 5块钱的时候怎么报价？
    

    
    
    

LOL罗辑思维全国人大代表真三搞笑视频柳岩