编程知识 cdmana.com

NOI/2.5 Basic Algorithm Search-6266: Picking Stones Game

Title

Total time limit: 1000ms Memory limit: 65536kB

Description

There are two piles of stones, and two people take turns to pick them. Each time they pick, they can only pick from the pile with the larger number, and the number must be an integer multiple of the number of stones from the pile with the smaller number.Whoever can empty a pile of stones will win.
For example, the number of two piles of stones at the beginning is 25 and 7

25 and 7 take stones
25 7-->11 7-->4 7-->4 3-->1 3-->1 0
Player 1 takesPlayer 2 takesPlayer 1 takesPlayer 2 takesPlayer 1 takes


In the end, player 1 (the first to take) wins. During the process of taking, player 2 has only one way to take it.
Given the initial number of stones, if both players take the optimal strategy, can the first player win.

Enter

The input contains most of the data.Each set of data has one row, including two positive integers a and b, which represent the number of stones at the beginning.
Input ends with two zeros.

Output

If the first player wins, output "win", otherwise output "lose"

Sample input

34 1215 240 0

Sample output

winlose

Tips

Assuming the number of stones is (a,b) and a >= b, if [a/b] >= 2, the first mover will win, if [a/b]<2, then there is only one way to take the first move.
[a/b] means the value of a divided by b rounded up.

It can be seen from the prompt that this question is a question of finding patterns.According to the hints and finding rules, we found that: assuming the number of stones is (a, b) and a >= b, if [a/b] >= 2, the first mover will win, and if a%b==0, the first mover will win.

Then complete the fun function.Among them, return !fun(b,a-b); uses the "subtraction method" to perfectly simulate the process of taking stones.

 int fun(int a,int b){if(a%b==0||a/b>=2)return 1;if(a/b<2)return !fun(b,a-b);}

Finally complete the main function.swap is a function that swaps two numbers.

 int main(){int a,b;while(1){cin>>a>>b;if(a==0&&b==0)return 0;if(a

Error-prone points

1. The recursive formula of fun.

2. For multiple sets of data, use while.

Complete program + comments

#includeusing namespace std;int fun(int a,int b){if(a%b==0||a/b>=2)return 1;if(a/b<2)return !fun(b,a-b);}int main(){int a,b;while(1){cin>>a>>b;if(a==0&&b==0)return 0;if(a

版权声明
本文为[mooczhimahu]所创,转载请带上原文链接,感谢
https://cdmana.com/2022/218/202208060731512027.html

Scroll to Top