#P16399. Finding the Top RPS Player
Finding the Top RPS Player
题目背景
“ACM Foods”准备在某个地区开设一家连锁店,而竞争对手“ICPC Pizza”也计划在同一地区开设分店。如果两家店距离过近,双方的收益都会受到影响。
经过协商,两家公司决定只允许其中一家开店,并通过石头剪刀布比赛决定最终的胜者。
ACM Foods 正面临财务困难,因此迫切希望赢得这次竞争。公司高层认为,能够连续获胜很多次的选手一定非常强,于是设计了一套特殊的选拔方案,希望找出一名达到指定连胜次数的选手。
题目描述
共有 名选手。每名选手都有一个当前的连续获胜次数,初始时所有人的连续获胜次数均为 。
比赛按轮进行。在同一轮中,可以同时安排任意多场比赛,但必须满足:
- 每场比赛只能由当前连续获胜次数相同的两名选手参加;
- 每名选手在同一轮中至多参加一场比赛;
- 每场比赛恰有一名获胜者和一名失败者;
- 获胜者的连续获胜次数增加 ;
- 失败者的连续获胜次数变为 。
例如,两名当前均为 连胜的选手进行比赛后,获胜者变为 连胜,失败者变为 连胜。
你可以自由决定每一轮安排哪些合法比赛。求最少需要多少轮,才能保证通过某种安排,使至少一名选手达到 次连续获胜。
输入格式
输入包含多组测试数据。
每组测试数据包含一行两个整数 :
- 表示选手人数;
- 表示目标连续获胜次数。
输入以一行两个整数 0 0 结束,该行不属于任何测试数据。
输出格式
对于第 组测试数据,输出一行:
Case i: answer
其中 answer 表示最少需要的轮数。
样例输入
2 1
10 5
15 10
0 0
样例输出
Case 1: 1
Case 2: 11
Case 3: 210
数据范围
对于所有测试数据: