Cod sursa(job #2018125)

Utilizator DjokValeriu Motroi Djok Data 3 septembrie 2017 16:23:06
Problema Bowling Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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(mex[x] != -1) return mex[x];

  vector<int> v;

  v.push_back(getMex(x - 1));
  v.push_back(getMex(x - 2));

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

  sort(v.begin(), v.end());

  int aux = 0;
  for(int i = 0; i < (int)v.size(); ++i) {
    if(v[i] != aux) break;
    while(i < (int)v.size() && v[i] == aux) ++i;
  }

  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;
}