RPS - Finding the Top RPS Player

no tags 

A company "ACM Foods" is preparing for opening its chain shop in a certain area, but another company "ICPC Pizza" is also planning to set up its branch shop in the same area. In general, two competitive shops gain less incomes if they are located so close to each other. Thus, if both "ACM Foods" and "ICPC Pizza" went on opening, they would be damaged financially. So, they had a discussion on this matter and made the following agreement: only one of them can branch its shop in the area. It is determined by Rock-Paper-Scissors (RPS) which to branch the shop.

ACM Foods is facing financial difficulties and strongly desires to open their new shop in that area. The executives have decided to make every effort for finding out a very strong RPS player. They believes that players who win consecutive victories must be strong players. In order to find such a player for sure, they have decided their simple strategy.

In this strategy, many players play games of RPS repeatedly, but the games are only played between players with the same number of consecutive wins. At the beginning, all the players have no wins, so any pair of players can play a game. The games can be played by an arbitrary number of pairs simultaneously. Let us call a set of simultaneous games as a turn. After the first turn, some players will have one win, and the other players will remain with no wins. In the second turn, some games will be played among players with one win, and some other games among players with no wins. For the former games, the winners will have two consecutive wins, and the losers will lose their first wins and have no consecutive wins. For the latter games, the winners will have one win, and the losers will remain with no wins. Therefore, after the second turn, the players will be divided into three groups: players with two consecutive wins, players with one win, and players with no wins. Again, in the third turn, games will be played among players with two wins, among with one win, and among with no wins. The following turns will be conducted so forth. After a sufficient number of turns, there should be a player with the desired number of consecutive wins.

The strategy looks crazy? Oh well, maybe they are confused because of their financial difficulties. Of course, this strategy requires an enormous amount of plays. The executives asked you, as an employee of ACM Foods, to estimate how long the strategy takes. Your task is to write a program to count the minimum number of turns required to find a player with M consecutive wins among N players.

Input

The input consists of multiple test cases. Each test case consists of two integers N (2 ≤ N ≤ 20) and M (1 ≤ M < N) in one line.

The input is terminated by the line containing two zeroes.

Output

For each test case, your program must output the case number followed by one integer which indicates the minimum number of turns required to find a person with M consecutive wins.

Example

Input:
2 1
10 5
15 10
0 0

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

hide comments
ferol: 2017-02-28 08:18:06

I think so
0 wins 1 win 2 win
1turn 15 0 0
2turn 8 7 0
3turn 7 5 3

Last edit: 2017-02-28 08:18:41
rsd_unleashed: 2015-05-19 18:06:41

Can someone explain case 3?When n is odd,in at the end of 1st turn there are 7 players with 1 win,7 with o win,1 who didn't play.So how does 2nd turn happen?

Richard: 2010-08-24 08:41:01

May I suggest changing Rock Paper Scissors into 'Coin Flipping'. With RPS there is the possibility of a tie. So you cannot say that with two players there is only 1 turn required to determine a player with 1 consecutive wins. You can only calculate the probability of such an event.

Of course, you can say that with this particalur version of RPS there is always a winner, but that seems a bit far fetched to me.

ymGXX: 2010-04-23 12:19:56

Enumerate!Enumerate!Enumerate!

Paul Draper: 2009-04-30 18:11:07

Note: The companies choose once any number of people reach M consecutive wins (i.e. there may be more than one player who matches the criteria).

Last edit: 2009-04-30 18:12:11

Added by:Bin Jin
Date:2008-09-08
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:JAG wintercamp 08, day2