#include #include #include #include #include using namespace std; #define N 1009 int A[N]; typedef long long LL; void generate_permutation(int n, vector* out) { out->resize(5 * n); vector& A = *out; for (int i = 0; i < n; ++i) { A[2 * i] = 5 * i; A[2 * i + 1] = 5 * i + 1; A[2 * n + 2 * i] = 5 * i + 2; A[2 * n + 2 * i + 1] = 5 * i + 3; A[4 * n + i] = 5 * i + 4; } } bool is_prime(int n) { for (int i = 2; i * i <= n; ++i) if (n % i == 0) return false; return true; } void calc_cycles(const vector& perm, vector >* out) { vector >& cycles = *out; vector v; v.assign(perm.size(), 0); for (int i = 0; i < perm.size(); ++i) { if (!v[i]) { cycles.push_back(vector()); vector& cycle = cycles.back(); int u = i; do { v[u] = 1; cycle.push_back(u); u = perm[u]; } while (u != i); } } } bool is_unique(const vector& a) { for (int i = 1; i < a.size(); i++) { if (a[i] != a[0]) return false; } return true; } int field_of_player(const vector &cycle, int n, int player) { int res = 0; for (int i = 0; i < cycle.size(); ++i) { if (cycle[i] / 5 == player) res ++; } return res; } struct Player { vector > constraints; int good; Player() { good = 0; } }; vector P; void process_cycle(int n, const vector& cycle) { //printf("Processing cycle: "); //for (int i = 0; i < cycle.size(); ++i) // printf("%d ", cycle[i]); //printf("\n"); vector good; for (int i = 0; i < cycle.size(); ++i) { if (A[cycle[i]] <= 5) good.push_back(i); } if (good.size() == 0) return; //printf("good "); //for (int k = 0; k < good.size(); k++) printf("%d ", good[k]); printf("\n"); map > players; for (int i = 0; i < cycle.size(); ++i) { vector p; for (int j = 0; j < good.size(); ++j) { int player = cycle[(good[j] + i) % cycle.size()] / 5; p.push_back(player); } //for (int k = 0; k < p.size(); k++) printf("%d ", p[k]); printf("\n"); if (is_unique(p) && field_of_player(cycle, n, p[0]) == good.size()) { players[ p[0] ].push_back(i); } } for (map >::iterator it = players.begin(); it != players.end(); ++it) { if (it->second.size() == 1){ P[it->first].constraints.push_back(make_pair(it->second[0], cycle.size())); P[it->first].good += good.size(); } if (it->second.size() > 1) { P[it->first].constraints.push_back(make_pair(it->second[0], cycle.size() / good.size())); P[it->first].good += good.size(); } //printf("%d -> x = %d (mod %d)\n", it->first, it->second[0], cycle.size()); } } LL gcd(LL a, LL b, LL &l, LL &k) { if(!a) { l = 0; k = 1; return b; } LL d = gcd(b % a, a, k, l); l -= (b / a) * k; return d; } // x = a (mod p) // x = b (mod q) // // x = res (mod pq/nwd) vector > solve(long long a, long long p, long long b, long long q) { LL x, y, c; LL r = gcd(p, q, x, y); if ((a - b) % r) return vector >(); x = a + p * (b-a) / r * x; r = p * q / r; c = x % r; if (c < 0) c += r; vector > res; res.push_back(make_pair(c, r)); return res; } void when_rec(LL a, LL q, int i, const Player& player, vector >& res) { if (i == player.constraints.size()) { res.push_back(make_pair(a, q)); return; } vector > www = solve(a, q, player.constraints[i].first, player.constraints[i].second); for (int j = 0; j < www.size(); j++) { when_rec(www[j].first, www[j].second, i + 1, player, res); } } long long when(const Player& player) { vector > res; when_rec(player.constraints[0].first, player.constraints[0].second, 1, player, res); LL best = res[0].first; for (int i = 0; i < res.size(); ++i) { if (res[i].first == 0) { printf("%d", res[i].second); res[i].first = res[i].second; } if(res[i].first < best) best = res[i].first; } //for (int i = 0; i < player.constraints.size(); ++i) { // printf("x = %d (mod %d)\n", player.constraints[i].first, player.constraints[i].second); //} return best; } void solve(int n) { P.clear(); P.resize(n); vector > cycles; vector perm; generate_permutation(n, &perm); calc_cycles(perm, &cycles); for (int i = 0; i < cycles.size(); ++i) { process_cycle(n, cycles[i]); } int player = -1; long long res = -1; for (int i = 0 ; i < n; ++i) { if (P[i].good == 5) { long long x = when(P[i]); if (res == -1 || x < res) { player = i; res = x; } } } if (res == -1) printf("Neverending game.\n"); else { printf("Player %d wins game number %lld.\n", player + 1, res); } //for (int i = 0; i < cycles.size(); ++i) { // for (int j = 0 ; j < cycles[i].size(); ++j ) // printf("%d ", cycles[i][j]); // printf("\n"); //} } int main() { while(1) { int n; scanf("%d", &n); if (n == 0) break; for (int i = 0; i < 5 * n; ++i) scanf("%d" , &A[i]); solve(n); } return 0; }