/* Shut the Box, MCPC 2011 Problem F, Java solution by Michael Goldwasser */ import java.util.*; import java.io.File; class shutMichael { static final int MAX_N = 22; static final int MAX_VAL = 22; static int N = MAX_N; // actual N for current trial static ArrayList> choices; // choices.get(v) is set of possible turn codes for value v //-------------------- utilities for piece codes ------------------------ // We use int as bitfield to code which pieces are unmarked, with bit for // 2^{p-1} being set if piece p is unmarked (i.e., least significant // bit is piece 1). We will also use these codes to describe subsets // of pieces that can be marked during a single turn. // Return true if piece p is unmarked public static boolean unmarked(int code, int p) { return (code & (1 << (p-1))) > 0; // bit is set } // returns true if every piece of turn is unmarked public static boolean legal(int code, int turn) { return ((code & turn) == turn); // i.e. turn is subset of code } // return new code with extra piece marked public static int markPiece(int code, int p) { return code | (1 << (p-1)); // clear the bit } // return new code based on marking pegs from given turn (assuming legal) public static int reduce(int code, int turn) { return (code ^ turn); // exclusive or } // Returns number of marked pegs public static int numMarked(int code) { int total = 0; for (int p=1; p <= N; p++) if (!unmarked(code,p)) total++; return total; } // Returns sum of the values of those pieces marked in the code public static int pegSum(int code) { int total = 0; for (int p=1; p <= N; p++) if (unmarked(code,p)) total += p; return total; } // this function only needs to be called once, to precompute list of choices public static void initChoices() { choices = new ArrayList>(); for (int j=0; j < 1+MAX_VAL; j++) choices.add(new ArrayList()); int half = MAX_VAL / 2; int halfcode = 1 << half; // to save time, we will only cycle through codes for bottom half of pegs. // can use at most one other peg. for (int code = 0; code < halfcode; code++) { int total = pegSum(code); if (total <= MAX_VAL) { choices.get(total).add(code); for (int p = half+1; p <= MAX_VAL; p++) { if (total + p <= MAX_VAL) choices.get(total+p).add(markPiece(code,p)); else break; } } } } public static void main(String[] args) throws java.io.FileNotFoundException { Scanner in = new Scanner(new File("shut.in")); initChoices(); int game = 1; while (true) { ArrayList turns = new ArrayList(); N = in.nextInt(); int T = in.nextInt(); if (N == 0) break; for (int k=0; k < T; k++) turns.add(in.nextInt()); Set reachable = new HashSet(); int initial = (1 << N) - 1; // all N pegs unmarked int mostMarked = 0; reachable.add(initial); for (int t=0; t < T; t++) { int turn = turns.get(t); Set newReach = new HashSet(); for (int curCode : reachable) { for (int k = 0; k < choices.get(turn).size(); k++) { int subset = choices.get(turn).get(k); if (legal(curCode,subset)) { int newCode = reduce(curCode,subset); newReach.add(newCode); int score = numMarked(newCode); if (score > mostMarked) mostMarked = score; } } } reachable = newReach; if (reachable.size() == 0) break; // no reason to continue } System.out.println("Game " + game++ + ": " + mostMarked); } } }