Cod sursa(job #1992060)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 19 iunie 2017 12:09:44
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
#define MAXN 50002

int mex[MAXN + 1];
bool viz[MAXN + 1];

int solve(int n) {
    if(n <= 0)
      return 0;
    if(viz[n] == 1)
      return mex[n];
    std::vector <int> v;
    viz[n] = 1;
    v.push_back(solve(n - 1));
    v.push_back(solve(n - 2));
    for(int i = 1; i <= n - 2; i++)
      v.push_back(solve(i) ^ solve(n - i - 1));
    for(int i = 1; i <= n - 3; i++)
      v.push_back(solve(i) ^ solve(n - i - 2));
    std::sort(v.begin(), v.end());
    if(v[0] != 0)
       mex[n] = 0;
    for(int i = 1; i < v.size(); i++)
       if(v[i] - v[i - 1] > 1) {
          mex[n] = v[i - 1] + 1;
          return mex[n];
       }
    mex[n] = v.back() + 1;
    return mex[n];

}

int main() {
    FILE *fi, *fout;
    int t, i, n, x;
    fi = fopen("bowling.in" ,"r");
    fout = fopen("bowling.out" ,"w");
    fscanf(fi,"%d " ,&t);
    viz[0] = 1;
    for(i = 1; i <= 200; i++)
       mex[i] = solve(i);
    while(t > 0) {
       t--;
       fscanf(fi,"%d " ,&n);
       int cnt = 0;
       int ans = 0;
       for(i = 1; i <= n; i++) {
          fscanf(fi,"%d " ,&x);
          if(x == 1)
            cnt++;
          else {
            if(cnt > 181)
              ans ^= mex[181 + (cnt - 181) % 12];
            else
              ans ^= mex[cnt];
            cnt = 0;
          }
       }
       if(cnt > 181)
          ans ^= mex[181 + (cnt - 181) % 12];
       else
          ans ^= mex[cnt];
       if(ans == 0)
          fprintf(fout,"Fumeanu\n");
       else
          fprintf(fout,"Nargy\n");
    }
    fclose(fi);
    fclose(fout);
    return 0;
}