Cod sursa(job #2238750)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 7 septembrie 2018 13:09:52
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 50005;

int i, t, n, x, mex[N], rs, cnt;

int getMex(int x) {
  if(x > 72) x = 73 + (x - 73) % 12;
  if(mex[x] != -1) return mex[x];

  set<int> S;

  S.insert(getMex(x - 1));
  S.insert(getMex(x - 2));

  for(int i = 1; i <= x / 2 + 1; ++i) {
    S.insert(getMex(i) ^ getMex(x - i - 1));
    S.insert(getMex(i) ^ getMex(x - i - 2));
  }

  int aux = 0;
  for(auto it : S)
    if(it == aux) ++aux;
    else break;

  return mex[x] = aux;
}

int main() {
  ifstream cin("bowling.in");
  ofstream cout("bowling.out");
  ios_base::sync_with_stdio(0);

  memset(mex, -1, sizeof(mex));
  for(i = 0; i < 3; ++i) mex[i] = i;

  for(cin >> t; t; --t) {
    cin >> n; rs = cnt = 0;
    for(i = 1; i <= n; ++i) {
      cin >> x;
      if(!x) rs ^= getMex(cnt), cnt = 0;
      else ++cnt;
      if(i == n) rs ^= getMex(cnt);
    }

    cout << (!rs ? "Fumeanu" : "Nargy") << '\n';
  }

  return 0;
}