Stoned Game

Created by LXC on Mon Mar 18 21:09:58 2024

https://codeforces.com/problemset/problem/1396/B

ranting: 1800

tag: brute force, constructive algorithms, games, greedy

problem

有n堆石子，每堆分别有$a_i$个石子。

两者轮流取其中一个石子。但不能取上次对手取过的那一堆。特殊的，第一次取可以取任何一堆的石子。

当前先手取完要取的石子之后使对手无路可走时，先手获胜。

t组数据，每组数据给出n和a，输出谁必会胜利。若先手胜利输出“T”，若后者胜利输出“HL”。无引号。

数据范围请参考原题。

solution

当有一堆多于整体总和的一半，那么先手必胜，先手可以一直拿最高的一堆。

否则，如果总和是奇数，那么先手永远拿剩余最高堆中的一个，最后一定能拿到最后一个，先手必胜。而总和是偶数则必败。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i:a) cin >> i;
    int s = accumulate(a.begin(), a.end(), 0);
    for (int i:a) {
        if (i>s/2) {
            cout << "T\n";
            return ;
        }
    }
    cout << (s%2?"T\n":"HL\n");
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}