Problem 1476 --Alice&Marisa

1476: Alice&Marisa

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 博弈

Alice和Marisa是一对好CP。Alice和Marisa都要向同一个商人Reimu购买节操。Reimu手中有 N 份节操,她会将它们一份份地卖给她们,Alice和Marisa通过竞价的方式来决定节操的归属。具体的过程如下:Reimu首先指定其中一个人开始报价,之后两人轮流报价,要求是一定要比对方报的价格更高。任何时候,如果一个人不愿出价或者出不起价钱时,可以宣布弃权,则对手以最后一次报的价格将节操买下。当然,如果两人都没钱,Reimu是不会卖节操的。首次报价至少为 1,并且只能报整数的价钱。

Alice 和Marisa特别爱攀比,因此她们都希望能比对方买到更多的节操。Alice和Marisa各自带了 CA 和 CM 的钱用于竞拍节操。此外,Marisa和Reimu有很不错的私人关系,因此Reimu总是会让Marisa先报价。现在请问,在Alice和Marisa都用最优策略的情况 下,谁能买到更多节操?假设双方都知道对方手中的现金数量,以及Reimu将要拍卖的节操数量 N。

本题有多组数据。每组数据为一行三个用空格隔开的整数 N,CM,CA,表示节操的数量,以及双方带的现金数量。0 ≤ N ≤ 100 000; 0 < CM, CA ≤ 1000000

对于每组测试数据,输出一行X,X的取值为{-1, 0, 1},-1表示Alice买到的节操会比Marisa多,0表示两人能买到一样多,1表示Marisa能买到更多节操。

4 3 5
7 4 7
0
1

推荐代码 查看1476 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 董学成 429616 2019-05-16 19:47:36
内存最少[$1116 $KB] 董学成 429616 2019-05-16 19:47:36
第一AC 未实名用户 89119 2017-05-15 16:17:14
第一挑战 未实名用户 89119 2017-05-15 16:17:14

赛题来源/所属竞赛 2013 Anhui College Student Programming Contest N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛