Cod sursa(job #2018264)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 4 septembrie 2017 10:36:43
Problema Bowling Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
#include <queue>
#include <ctime>
#include <unordered_map>
#include <set>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "bowling"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

const int MAXN = 50010;
int g[MAXN];
set<int> S;

int compute(int x);

void reachable(int x) {
  S.clear();
  if (x > 0)
    S.insert(compute(x - 1));
  if (x > 1)
    S.insert(compute(x - 2));
  for (int left = 1; left < x; ++left) {
    int right = x - left - 1;
    if (right > 0)
      S.insert(compute(left) ^ compute(right));
    right = x - left - 2;
    if (right > 0)
      S.insert(compute(left) ^ compute(right));
  }
}

int compute(int x) {
  if (g[x] >= 0)
    return g[x];
  reachable(x);
  int mex = 0;
  for (const auto &it : S)
  if (mex == it) ++mex;
  else break;
  return g[x] = mex;
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  memset(g, 0xFF, sizeof(g));
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    int ans = 0, cur = 0;
    for (int i = 0; i <= N; ++i) {
      if (i < N) {
        int x; scanf("%d", &x);
        if (x > 0) {
          ++cur;
          continue;
        }
      }
      ans ^= compute(cur);
      cur = 0;
    }
    puts(ans ? "Nargy" : "Fumeanu");
  }
  return 0;
}