# A simple stone game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 312    Accepted Submission(s): 167

Problem Description

After he has learned how to play Nim game, Mike begins to try another stone game which seems much easier. The game goes like this: Two players start the game with a pile of n stones. They take stones from the pile in turn and every time they take at least one stone. The one who goes first can take at most n-1 stones for his first move. From then on a player can take at most k times as many stones as his opponent has taken last time. For example, if one player take m stones in his turn, then the other player can take at most k × m stones next time. The player who takes the last stone wins the game. Suppose that those two players always take the best moves and never make mistakes, your job is to find out who will definitely win the game.

Input

The first line contains a integer t, indicating that there are t test cases following.(t<=20). Each test case is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).

Output

For each test case, output one line starting with “Case N: ”, N is the case number. And then, if the first player can ensure a winning, print the minimum number of stones he should take in his first turn. Otherwise, print "lose". Please note that there is a blank following the colon.

Sample Input

5

16 1

11 1

32 2

34 2

19 3

Sample Output

Case 1: lose

Case 2: 1

Case 3: 3

Case 4: lose

Case 5: 4

Source

2008 Asia Regional Beijing

``` 1 #include<stdio.h>
2 #define maxn 1000000
3 int n , k ;
4
5 int a[maxn+1];
6 int r[maxn+1];
7 void solve()
8 {
9     int i,j;
10     a[0]=a[0]=0;
11     for(i=1,j=0 ;i<=maxn;i++)
12     {
13         a[i]=r[i-1]+1;
14         while(j+1<i && a[j+1]*k<a[i])
15             j++;
16         r[i]=a[i]+r[j];
17         if(r[i]>=n) break;
18     }
19     if(i>maxn)
20     {
21         printf("un solvable\n");
22         return ;
23     }
24     if(a[i]==n)
25     {
26         printf("lose\n");
27         return ;
28     }
29     for( ; i>=1 ;i--)
30     {
31         if(n==a[i])
32         {
33             printf("%d\n",n);
34             return ;
35         }
36         else if(n>a[i]) n-=a[i];
37     }
38     printf("logic error\n");
39 }
40 int  main()
41 {
42     int ca ,cc=0;
43     scanf("%d",&ca);
44     while(ca-->0)
45     {
46         scanf("%d %d",&n,&k);
47         printf("Case %d: ",++ cc);
48         solve();
49     }
50     return 0;
51 }```

0 条评论

## 相关文章

### HDU 1103 Flo's Restaurant(模拟+优先队列)

Flo's Restaurant Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/...

29360

### HDU 1004 Let the Balloon Rise【STL<map>】

Let the Balloon Rise Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...

31040

### HDUOJ------Daydream字符查找-并求其始末位置

2013-07-17  10:50:38 Daydream Time Limit: 2000/1000 MS (Java/Others)    Memory L...

29360

### hdu 3038 How Many Answers Are Wrong ( 带 权 并 查 集 )

How Many Answers Are Wrong Time Limit: 2000/1000 MS (Java/Others)    Memory Limi...

37370

Grade Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 262144/262144 K (J...

33290

### HDUOJ 1099——Lottery

Lottery Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

37170

### ＨＤＵＯＪ－－－What Are You Talking About

What Are You Talking About Time Limit: 10000/5000 MS (Java/Others)    Memory Lim...

402140

### HDU 1885 Key Task(BFS)

Key Task Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

36540

### POJ-1276-Cash Machine（多重背包）

Cash Machine Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

29140

### HDUOJ--1058HangOver

HangOver Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (...

29360