#P16399. Finding the Top RPS Player

Finding the Top RPS Player

题目背景

“ACM Foods”准备在某个地区开设一家连锁店,而竞争对手“ICPC Pizza”也计划在同一地区开设分店。如果两家店距离过近,双方的收益都会受到影响。

经过协商,两家公司决定只允许其中一家开店,并通过石头剪刀布比赛决定最终的胜者。

ACM Foods 正面临财务困难,因此迫切希望赢得这次竞争。公司高层认为,能够连续获胜很多次的选手一定非常强,于是设计了一套特殊的选拔方案,希望找出一名达到指定连胜次数的选手。

题目描述

共有 NN 名选手。每名选手都有一个当前的连续获胜次数,初始时所有人的连续获胜次数均为 00

比赛按轮进行。在同一轮中,可以同时安排任意多场比赛,但必须满足:

  1. 每场比赛只能由当前连续获胜次数相同的两名选手参加;
  2. 每名选手在同一轮中至多参加一场比赛;
  3. 每场比赛恰有一名获胜者和一名失败者;
  4. 获胜者的连续获胜次数增加 11
  5. 失败者的连续获胜次数变为 00

例如,两名当前均为 kk 连胜的选手进行比赛后,获胜者变为 k+1k+1 连胜,失败者变为 00 连胜。

你可以自由决定每一轮安排哪些合法比赛。求最少需要多少轮,才能保证通过某种安排,使至少一名选手达到 MM 次连续获胜。

输入格式

输入包含多组测试数据。

每组测试数据包含一行两个整数 N,MN,M

  • NN 表示选手人数;
  • MM 表示目标连续获胜次数。

输入以一行两个整数 0 0 结束,该行不属于任何测试数据。

输出格式

对于第 ii 组测试数据,输出一行:

Case i: answer

其中 answer 表示最少需要的轮数。

样例输入

2 1
10 5
15 10
0 0

样例输出

Case 1: 1
Case 2: 11
Case 3: 210

数据范围

对于所有测试数据:

2N20,2\le N\le 20, 1M<N.1\le M<N.