【湖南大学2018年第十四届程序设计竞赛重现赛】A - game

末蓝、 2022-05-23 03:17 136阅读 0赞

## 题目描述 ##

[题目传送门 - 牛客网][-]

时间限制：C/C++ 1秒，其他语言2秒  
空间限制：C/C++ 65536K，其他语言131072K  
64bit IO Format: %lld

**题目描述**

Tony and Macle are good friends. One day they joined a birthday party together. Fortunately, they got the opportunity to have dinner with the princess, but only one person had the chance. So they decided to play a game to decide who could have dinner with the princess.

The rules of the game are very simple. At first, there are n sticks. Each of exactly m meters in length. Each person takes turns. For one move the player chooses just one stick and cut it into several equal length sticks, and the length of each stick is an integer and no less than k. Each resulting part is also a stick which can be chosen in the future. The player who can’t make a move loses the game ,thus the other one win.  
Macle make the first move.

**输入描述:**

the first line contains tree integer n,m,k(1 <= n,m,k <= 109)

**输出描述:**

print ‘Macle’ if Macle wins or ‘Tony’ if Tony wins,you should print everything without quotes.

**示例1**

输入

1 15 4

输出

Macle

**示例2**

输入

4 9 5

输出

Tony

## 题意分析 ##

大体来说，这道题目对于我这种英语渣来说理解还是有一定的难度，当时是翻字典，多次反复读才真正的明白了题意。（英语渣伤不起呀 ~\_~）

大概的题意是：给定了n根长度为m的线段，将线段分割为等长的各段，求能分割奇数次还是偶数次？（有些细节就没有说了，直接读原题吧）

**坑点：**

这道题目我觉得最坑的在于题目给我们的信息量少，我们需要分析才能知道题意或者才能找到高效的解决方案(当然，说明了题目出的好，55555555)。还有一个坑点，或者说我认为这道题目出的不好的一个点是输入样例结束没有阐述。。。

此题我觉得我们需要明确几个问题：

1、应该将线段分割为多少段？  
2、分割的次数是奇数时，谁赢？

总的来说就两个问题，对于第二个问题呢没有什么好说的，看题目就能够明白了。

主要是对于第一个问题，应该将线段分割为多少段呢?或者说每一次如何进行分割呢？我们分析下，假设线段长 m = 100，k = 20,那么总共有以下分法：

1、直接分为 5 \* 20 （分割1次）  
2、直接分为 4 \* 25 （分割1次）  
3、先分为 2 \* 50 ， 再分为 2 \* 25 （分割3次）

结果发现，都是奇数次 ，如果k再小点，也就是分割的层数（比如第一种情况为一层，第三种情况为二层）每多增加一层，其实都是再增加偶数次的分割次数，也就是并不会影响总的分割次数的奇偶性。

## AC代码 ##

#include <bits/stdc++.h>
    using namespace std;
    int main(){
        int n,m,k;
        cin>>n>>m>>k;
        if(n % 2 == 0){
            cout<<"Tony"<<endl;
        } else{
            bool flag = false;
            for(int i=m/k;i>1;i--){
                if(m % i == 0){
                    flag = true;
                    break;
                }
            }
            if(flag){
                cout<<"Macle"<<endl;
            } else{
                cout<<"Tony"<<endl;
            }
        }
        return 0;
    }

**代码解释**

注意看对于 n 的奇偶性的判断，试想一下，如果 n 为偶数，那么不管每条线段能不能分割，那么总的分割次数总为 偶数次，

如果 n 为奇数的情况下，那么，如果线段能够进行分割，那么必定为 奇数次分割，奇数 \* 奇数 = 奇数，则总的分割次数为 奇数次 ； 如果不能分割，即题目给定的 Macle为先，则Tony 获胜

**注：** 如有错误之处，还望dalao指正，谢谢

[-]: https://www.nowcoder.com/acm/contest/125/A