Circle Game

Circle Game

Problem - B - Codeforces

题意

有$n$堆石子两个人轮流游戏，假设$A$在$i$操作了则$B$下一次在$(i+1)\%n+1$的位置操作，每个人每次可以大于$1$的任意大于$0$的石子，当某个人无法操作则这个人输，$A$先手且从位置$1$开始，问你两人均操作最优情况下谁赢

思路

• 贪心

如果$n$是奇数，$A$必胜，因为$A$把第$1$堆都拿走，然后走一圈回来$B$会在第$1$堆操作这个时候没法操作了

如果$n$是偶数，两个人能操作的位置是固定的$A$只能在奇数位置轮流操作，$B$只能在偶数位置轮流操作，因此我们找到第一个最小是看是奇数还是偶数位置即可

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {
    -1, 0, 1, 0}, dy[] = {
    0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
LL a[N];
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
    
        cin >> n;
        LL s1 = 2e9;
        idx = 0;
        for (int i = 1; i <= n; i ++) {
    
            cin >> a[i];
            if (a[i] < s1) s1 = a[i], idx = i;
        }
        
        if (n & 1) cout << "Mike\n";
        else {
    
            if (idx & 1) cout << "Joe\n";
            else cout << "Mike\n";
        }
    }
    return 0;
}