import java.util.Arrays; import java.util.Scanner; public class Main { private static final long[] masks = new long[1 << 6]; static { for (int mask = 0; mask < (1 << 6); mask++) { long m = 0L; for (int i = 0; i < 6; i++) { if ((mask & (1 << i)) == 0) { continue; } m |= (63L << (6 * i)); } masks[mask] = m; } } private int[] dice_mask = new int[36]; private long[] dice_count = new long[36]; private int score = (int) -1e18; private int[][] table = new int[6][6]; private int bestScore = (int) -1e18; private int[][] bestTable = new int[6][6]; private SAState sa = new SAState(); private int[] part_score_row = new int[6]; private long[] counts_row = new long[6]; private int[] part_score_column = new int[6]; private long[] counts_column = new long[6]; private int[][] remove_row = new int[6][6]; private int[][] remove_column = new int[6][6]; public static void main(String[] args) throws Exception { new Main().run(); } private void run() { read(); solve(); write(); } private void read() { try (final Scanner in = new Scanner(System.in)) { for (int i = 0; i < 36; i++) { for (int j = 0; j < 6; j++) { int dice = in.nextInt() - 1; dice_mask[i] |= (1 << dice); dice_count[i] += (1L << (dice * 6)); if (i == 0 && j == 0) { Constants.watch.init(); } } } } catch (Exception e) { e.printStackTrace(); } } private void solve() { greedy(); multiSA(); Utils.debug(bestScore, sa.numIterations); } private void greedy() { for (int r = 0; r < 6; r++) { for (int c = 0; c < 6; c++) { table[r][c] = r * 6 + c; counts_row[r] += dice_count[table[r][c]]; counts_column[c] += dice_count[table[r][c]]; } } update_remove(); score = calculateScore(); saveBest(); } private void saveBest() { if (score > bestScore) { bestScore = score; for (int r = 0; r < 6; r++) { for (int c = 0; c < 6; c++) { bestTable[r][c] = table[r][c]; } } } } private void restoreBest() { for (int i = 0; i < 6; i++) { counts_row[i] = 0; counts_column[i] = 0; } for (int r = 0; r < 6; r++) { for (int c = 0; c < 6; c++) { table[r][c] = bestTable[r][c]; counts_row[r] += dice_count[table[r][c]]; counts_column[c] += dice_count[table[r][c]]; } } update_remove(); score = calculateScore(); } private void multiSA() { int numRestart = 100; double startTime = Constants.watch.getSecond(); double endTime = 1.8; double remainTime = endTime - startTime; double startStartTemperature = 2; double endStartTemperature = 0.5; for (double restart = 0; restart < numRestart; restart++) { sa.startTime = startTime + remainTime * restart / numRestart; sa.endTime = startTime + remainTime * (restart + 1) / numRestart; sa.startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart); sa.endTemperature = 0.5; SA(); restoreBest(); } } private void SA() { sa.init(); for (;; ++sa.numIterations) { if ((sa.numIterations & ((1 << 10) - 1)) == 0) { sa.update(); if (sa.isTLE()) { break; } } mutate(); } } private void mutate() { swap(); } private void swap() { int v1 = sa.numIterations % 36; final int r1 = v1 / 6; final int c1 = v1 % 6; int v2 = Constants.RNG.nextInt(35); if (v2 >= v1) { v2++; } final int r2 = v2 / 6; final int c2 = v2 % 6; final int current1 = table[r1][c1]; final int current2 = table[r2][c2]; int before = 0; int after = 0; int after_r1 = 0; int after_r2 = 0; int after_c1 = 0; int after_c2 = 0; if (r2 != r1) { before += part_score_row[r1]; before += part_score_row[r2]; after_r1 = partScore(remove_row[r1][c1] & dice_mask[current2], counts_row[r1] - dice_count[current1] + dice_count[current2]); after_r2 = partScore(remove_row[r2][c2] & dice_mask[current1], counts_row[r2] - dice_count[current2] + dice_count[current1]); after += after_r1; after += after_r2; } if (c2 != c1) { before += part_score_column[c1]; before += part_score_column[c2]; after_c1 = partScore(remove_column[r1][c1] & dice_mask[current2], counts_column[c1] - dice_count[current1] + dice_count[current2]); after_c2 = partScore(remove_column[r2][c2] & dice_mask[current1], counts_column[c2] - dice_count[current2] + dice_count[current1]); after += after_c1; after += after_c2; } int deltaScore = after - before; if (sa.accept(deltaScore)) { score += deltaScore; table[r1][c1] = current2; table[r2][c2] = current1; if (r2 != r1) { part_score_row[r1] = after_r1; part_score_row[r2] = after_r2; counts_row[r1] -= dice_count[current1]; counts_row[r2] -= dice_count[current2]; counts_row[r1] += dice_count[current2]; counts_row[r2] += dice_count[current1]; } if (c2 != c1) { part_score_column[c1] = after_c1; part_score_column[c2] = after_c2; counts_column[c1] -= dice_count[current1]; counts_column[c2] -= dice_count[current2]; counts_column[c1] += dice_count[current2]; counts_column[c2] += dice_count[current1]; } update_remove(r1, c1, r2, c2); saveBest(); } else { } } private void update_remove() { for (int r = 0; r < 6; r++) { for (int c = 0; c < 6; c++) { { int mask = -1; for (int r2 = 0; r2 < 6; r2++) { if (r2 == r) { continue; } mask &= dice_mask[table[r2][c]]; } remove_column[r][c] = mask; } { int mask = -1; for (int c2 = 0; c2 < 6; c2++) { if (c2 == c) { continue; } mask &= dice_mask[table[r][c2]]; } remove_row[r][c] = mask; } } } } private void update_remove(int r3, int c3, int r4, int c4) { { int r = r3; for (int c = 0; c < 6; c++) { { int mask = -1; for (int r2 = 0; r2 < 6; r2++) { if (r2 == r) { continue; } mask &= dice_mask[table[r2][c]]; } remove_column[r][c] = mask; } { int mask = -1; for (int c2 = 0; c2 < 6; c2++) { if (c2 == c) { continue; } mask &= dice_mask[table[r][c2]]; } remove_row[r][c] = mask; } } } { int r = r4; for (int c = 0; c < 6; c++) { { int mask = -1; for (int r2 = 0; r2 < 6; r2++) { if (r2 == r) { continue; } mask &= dice_mask[table[r2][c]]; } remove_column[r][c] = mask; } { int mask = -1; for (int c2 = 0; c2 < 6; c2++) { if (c2 == c) { continue; } mask &= dice_mask[table[r][c2]]; } remove_row[r][c] = mask; } } } { int c = c3; for (int r = 0; r < 6; r++) { { int mask = -1; for (int r2 = 0; r2 < 6; r2++) { if (r2 == r) { continue; } mask &= dice_mask[table[r2][c]]; } remove_column[r][c] = mask; } { int mask = -1; for (int c2 = 0; c2 < 6; c2++) { if (c2 == c) { continue; } mask &= dice_mask[table[r][c2]]; } remove_row[r][c] = mask; } } } { int c = c4; for (int r = 0; r < 6; r++) { { int mask = -1; for (int r2 = 0; r2 < 6; r2++) { if (r2 == r) { continue; } mask &= dice_mask[table[r2][c]]; } remove_column[r][c] = mask; } { int mask = -1; for (int c2 = 0; c2 < 6; c2++) { if (c2 == c) { continue; } mask &= dice_mask[table[r][c2]]; } remove_row[r][c] = mask; } } } } private int calculateScore() { int score = 0; for (int r = 0; r < 6; r++) { final int partScoreRow = partScoreRow(r); part_score_row[r] = partScoreRow; score += partScoreRow; } for (int c = 0; c < 6; c++) { final int partScoreColumn = partScoreColumn(c); part_score_column[c] = partScoreColumn; score += partScoreColumn; } return score; } private int partScoreRow(int r) { int mask = dice_mask[table[r][0]] & dice_mask[table[r][1]] & dice_mask[table[r][2]] & dice_mask[table[r][3]] & dice_mask[table[r][4]] & dice_mask[table[r][5]]; final long v = counts_row[r]; return partScore(mask, v); } private int partScoreColumn(int c) { int mask = dice_mask[table[0][c]] & dice_mask[table[1][c]] & dice_mask[table[2][c]] & dice_mask[table[3][c]] & dice_mask[table[4][c]] & dice_mask[table[5][c]]; final long v = counts_column[c]; return partScore(mask, v); } private int partScore(int mask, final long v) { long v2 = v & masks[mask]; v2 = (v2 >>> 6) + v2; v2 = (v2 >>> 12) + v2; v2 = (v2 >>> 24) + v2; return (int) ((Integer.bitCount(mask) * -3) + (v2 & 63)); } private void write() { String[] s = new String[36]; for (int i = 0; i < s.length; i++) { s[i] = ""; } for (int r = 0; r < 6; r++) { for (int c = 0; c < 6; c++) { s[bestTable[r][c]] = (r + 1) + " " + (c + 1); } } StringBuilder sb = new StringBuilder(); for (int i = 0; i < 36; i++) { sb.append(s[i]).append('\n'); } System.out.print(sb.toString()); System.out.flush(); } } class SAState { public static final boolean useTime = true; public double startTime; public double endTime; public double time; public double startTemperature; public double endTemperature; public double inverseTemperature; public double lastAcceptTemperature; public double startRange; public double endRange; public double range; public int numIterations; public int validIterations; public int acceptIterations; private double[] log = new double[32768]; public SAState() { for (int i = 0; i < log.length; i++) { log[i] = Math.log((i + 0.5) / log.length); } } public void init() { numIterations = 0; validIterations = 0; acceptIterations = 0; update(); lastAcceptTemperature = inverseTemperature; } public void update() { updateTime(); updateTemperature(); } public void updateTemperature() { double time0to1 = elapsedPercentage(startTime, endTime, time); double startY = startTemperature; double endY = endTemperature; double temperature = interpolate(startY, endY, time0to1); inverseTemperature = 1.0 / temperature; } private double elapsedPercentage(double min, double max, double v) { return (v - min) / (max - min); } private double interpolate(double v0, double v1, double d0to1) { return v0 + (v1 - v0) * d0to1; } public void updateRange() { range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0); } public void updateTime() { time = useTime ? Constants.watch.getSecond() : numIterations; } public boolean isTLE() { return time >= endTime; } public boolean accept(double deltaScore) { return acceptB(deltaScore); } public boolean acceptB(double deltaScore) { validIterations++; if (deltaScore > -1e-9) { acceptIterations++; return true; } double d = deltaScore * inverseTemperature; if (d < -10) { return false; } if (log[Constants.RNG.nextInt() & 32767] < d) { acceptIterations++; lastAcceptTemperature = inverseTemperature; return true; } return false; } public boolean acceptS(double deltaScore) { validIterations++; if (deltaScore < 1e-9) { acceptIterations++; return true; } double d = -deltaScore * inverseTemperature; if (d < -10) { return false; } if (log[Constants.RNG.nextInt() & 32767] < d) { acceptIterations++; lastAcceptTemperature = inverseTemperature; return true; } return false; } } final class Utils { private Utils() { } public static final void debug(Object... o) { System.err.println(toString(o)); System.err.flush(); } public static final String toString(Object... o) { return Arrays.deepToString(o); } public static boolean isValid(int v, int min, int minUpper) { return v >= min && v < minUpper; } } class Watch { private long start; public Watch() { init(); } public double getSecond() { return (System.nanoTime() - start) * 1e-9; } public void init() { init(System.nanoTime()); } private void init(long start) { this.start = start; } public String getSecondString() { return toString(getSecond()); } public static final String toString(double second) { if (second < 60) { return String.format("%5.2fs", second); } else if (second < 60 * 60) { int minute = (int) (second / 60); return String.format("%2dm%2ds", minute, (int) (second % 60)); } else { int hour = (int) (second / (60 * 60)); int minute = (int) (second / 60); return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60)); } } } interface Constants { Watch watch = new Watch(); PCG_XSH_RR RNG = new PCG_XSH_RR(System.nanoTime()); } final class PCG_XSH_RR { private long state = 5342; public PCG_XSH_RR(final long state) { this.state = state; } public int nextInt() { final long oldstate = state; state = oldstate * 6364136223846793005L + 521L; final int xorshift = (int) (((oldstate >>> 18) ^ oldstate) >>> 27); final int rotation = (int) (oldstate >>> 59); return (xorshift >>> rotation) | (xorshift << (-rotation & 31)); } public int nextInt(int n) { return (int) (n * nextDouble()); } public double nextDouble() { return (nextInt() >>> 1) * 4.6566128730773926E-10; } }