p153.ans1
======================
SECOND PLAYER MUST WIN


=================
p153.ans2
======================
FIRST PLAYER MUST WIN

=================
p153.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<int> p;

void read() {
    cin >> n >> m;
    p.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> p[i];
    }
    p.push_back(1);
}

void solve() {
    // This is a losing-last-match (misere) take-away game: dp[i] is 1 if the
    // player to move with i matches wins. Position i wins if some allowed move
    // x leads to a losing position dp[i - x] == 0; dp[0] = 1 encodes that
    // facing 0 matches means the opponent just took the last and lost. Since
    // moves take at most 9 matches, dp[i] depends only on the previous 10
    // values, so the sequence is eventually periodic. We pack the last 10
    // outcomes into a 10-bit state and record the first index each state
    // appears; on a repeat we know the cycle length and jump straight to the
    // equivalent index for n via modular arithmetic instead of iterating up to
    // 10^9.

    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());

    vector<int> pos_of_state(1 << 10, -1);

    vector<int> dp(min(1 << 13, n + 1), 0);
    dp[1] = 0;
    dp[0] = 1;

    int ans = -1;
    for(int i = 2; i <= n; i++) {
        for(int x: p) {
            if(x > i) {
                break;
            }
            if(dp[i - x] == 0) {
                dp[i] = 1;
                break;
            }
        }

        int state = 0;
        for(int prv = 0; prv < 10; prv++) {
            if(i - prv < 0 || dp[i - prv] == 1) {
                state |= (1 << prv);
            }
        }

        if(pos_of_state[state] == -1) {
            pos_of_state[state] = i;
        } else {
            int cycle_length = i - pos_of_state[state];
            int need = (n - i) % cycle_length;

            ans = dp[i - cycle_length + need];
            break;
        }
    }

    if(ans == -1) {
        ans = dp[n];
    }

    cout << (ans ? "FIRST PLAYER MUST WIN" : "SECOND PLAYER MUST WIN") << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p153.in1
======================
1
5 3
2 3 5

=================
p153.in2
======================
1
100000000 3
2 3 5

=================
statement.txt
======================
153. Playing with matches
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



Little boy Petya plays a game with his friend. They have a heap that consists of N (1<=N<=10^9) matches. It is possible to take 1,P1,P2,...,Pm (2<=Pi<=9, 0<=m<=8) matches from the heap.
Players take matches from the heap one by one. The player who takes the last match looses. Petya proved that for any set of N and Pi one of players has winning strategy, i.e. set of rules driving to a victory independently of opponent's moves. You task is to discover who has this strategy.

Input
Input file consist of K test cases. Natural number K is written in the first line. Every test case describes one game: numbers N and M are written in first line of every test case, and second line contains sequence Pi. All numbers in then input are integer numbers. So, if K=2, then second and third lines describe first game and fourth and fifth lines describe second game.

Output
For each test case write in the output file phrase FIRST PLAYER MUST WIN if first player have winning strategy, and SECOND PLAYER MUST WIN therwise.

Sample test(s)

Input
1
5 3
2 3 5

Output
SECOND PLAYER MUST WIN
Author:	Andrew V. Lazarev
Resource:	Saratov Subregional School Team Contest, 2002
Date:	Spring, 2002







=================
