/* * ACM ICPC - CERC 2011 * * Sample solution: Boring Card Game (cards) * Author: Martin Kacer */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.StringTokenizer; public class cards { StringTokenizer st = new StringTokenizer(""); BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws Exception { cards instance = new cards(); while (instance.run()) {/*repeat*/} } String nextToken() throws Exception { while (!st.hasMoreTokens()) st = new StringTokenizer(input.readLine()); return st.nextToken(); } int nextInt() throws Exception { return Integer.parseInt(nextToken()); } static final int MAXN = 1000; static int perm5cnt = 0; static final int[][] perm5 = new int[120][5]; static { int[] res = new int[5]; genperm5(res, 0, 0); } static void genperm5(int res[], int idx, int used) { if (idx == 5) { System.arraycopy(res, 0, perm5[perm5cnt++], 0, 5); return; } for (int i = 0; i < 5; ++i) if ((used & (1< 0) { BigInteger q[] = p1.divideAndRemainder(p2); BigInteger x0 = x2.subtract(x1.multiply(q[0])); BigInteger y0 = y2.subtract(y1.multiply(q[0])); x2 = x1; x1 = x0; y2 = y1; y1 = y0; p1 = p2; p2 = q[1]; } return new BigInteger[]{p1, x2, y2}; } void trackCard(int num, int pos) { int step = 0, p = pos; do { presence[num][p] = ++step; p = shufflePerm[p]; } while (p != pos); period[num] = step; } BigInteger testCombination(int[] cardpos) { for (int i = 0; i < 5; ++i) if (presence[i][cardpos[i]] == 0) return null; BigInteger p1 = BigInteger.valueOf(period[0]); BigInteger s1 = BigInteger.valueOf(presence[0][cardpos[0]] - 1); for (int i = 1; i < 5; ++i) { BigInteger p2 = BigInteger.valueOf(period[i]); BigInteger s2 = BigInteger.valueOf(presence[i][cardpos[i]] - 1); BigInteger[] ee = euclidean(p1, p2); BigInteger d = s2.subtract(s1); BigInteger[] dq = d.divideAndRemainder(ee[0]); if (dq[1].signum() != 0) return null; s1 = p1.multiply(ee[1]).multiply(dq[0]).add(s1); p1 = p1.divide(ee[0]).multiply(p2); s1 = s1.mod(p1); } return (s1.signum() == 0) ? p1 : s1; } int posOfCard[] = new int[5]; BigInteger testPlayer(int pos) { BigInteger best = null; for (int i = 0; i < perm5.length; ++i) { for (int j = 0; j < 5; ++j) posOfCard[j] = pos + perm5[i][j]; BigInteger c = testCombination(posOfCard); if (c != null && (best == null || best.compareTo(c) > 0)) best = c; } return best; } boolean run() throws Exception { int n = nextInt(); if (n == 0) return false; genPerm(n); presence = new int[5][5*n]; for (int i = 0; i < 5*n; ++i) { int c = nextInt(); if (c-- > 5) continue; trackCard(c, i); } int winner = 0; BigInteger best = null; for (int p = 0; p < n; ++p) { BigInteger win = testPlayer(5*p); if (win != null && (best == null || best.compareTo(win) > 0)) { best = win; winner = p+1; } } System.out.println((best == null) ? "Neverending game." : "Player " + winner + " wins game number " + best + "."); return true; } }