// Solution to "Domiyahtzee" import java.util.*; class Domino { public String ori; // orientation: H, V, or S public int n1, n2; // values on domino public int row,col; // location on the board public Domino(String o, int a, int b, int r, int c) { ori = o; n1 = a; n2 = b; row = r; col = c; } } public class C { public static Scanner in; public static int n; public static Domino dom[]; // the list of dominoes on the board public static boolean used[][]; // keeps track of which dominoes are used public static int board[][]; // the 5 by 5 board public static boolean first; // for keeping track of multiple yahtzees public static int count[]; // scoring--number of occurrences of each value public static int maxd,maxn1,maxn2,maxrow,maxcol; // currest best results public static void main(String[] args) { in = new Scanner(System.in); dom = new Domino[6]; // Read in the input: dom = new Domino[13]; n = in.nextInt(); for (int casenum = 1; casenum <= n; casenum++) { // Initially, no dominoes have been used: used = new boolean[6][]; for (int i = 0; i < 6; i++) { used[i] = new boolean[6]; Arrays.fill(used[i],false); } for (int i = 0; i < 13; i++) { String o = in.next(); int a = in.nextInt(); int b = 0; if (!o.equals("S")) { b = in.nextInt(); used[a-1][b-1] = true; // mark it as "used" used[b-1][a-1] = true; // symmetry } dom[i] = new Domino(o,a,b,0,0); } // Initialize the board: board = new int[5][]; for (int i = 0; i < 5; i++) { board[i] = new int[5]; Arrays.fill(board[i],0); } int k = 0; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { if (board[i][j] == 0) { board[i][j] = dom[k].n1; if (dom[k].ori.equals("H")) board[i][j+1] = dom[k].n2; else if (dom[k].ori.equals("V")) board[i+1][j] = dom[k].n2; dom[k].row = i; dom[k].col = j; k++; } } } /* DEBUG: System.out.println("Case " + casenum + ":"); for(int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { System.out.printf("%2d",board[i][j]); } System.out.println(); System.out.println("Unused dominos:"); for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) if (!used[i][j]) System.out.println("("+(i+1)+","+(j+1)+")"); System.out.println("Score = " + score()); */ int scr = solve(); if (maxd >= 0) //System.out.printf("Case %d: %d %d %d %d %d\n",casenum,dom[maxd].n1, // dom[maxd].n2,maxn1,maxn2,scr); System.out.printf("Case %d: %d\n",casenum, scr); else //System.out.printf("Case %d: -1 -1 -1 -1 %d\n",casenum,scr); System.out.printf("Case %d: %d\n",casenum,scr); } } public static int solve() { int maxscore = score(); maxd = -1; // For each domino on the board... for (int i = 0; i < dom.length; i++) { if (dom[i].ori.equals("S")) // don't try to replace the "solitary" cell continue; // ... try each unused domino (both orientations): for (int j = 0; j < 6; j++) { for (int k = 0; k < 6; k++) { if (!used[j][k]) { // Remember the domino being replaced: Domino temp = new Domino(dom[i].ori,dom[i].n1,dom[i].n2, dom[i].row,dom[i].col); // Replace it: board[temp.row][temp.col] = j+1; if(temp.ori.equals("H")) board[temp.row][temp.col+1] = k+1; else board[temp.row+1][temp.col] = k+1; // Calculate new score, see if it's better: int s = score(); if (s > maxscore) { // If better, remember which replacement caused it: maxscore=s; maxd = i; maxn1 = j+1; maxn2 = k+1; } // Restore the board: board[temp.row][temp.col] = temp.n1; if(temp.ori.equals("H")) board[temp.row][temp.col+1] = temp.n2; else board[temp.row+1][temp.col] = temp.n2; } } } } return maxscore; } // Score the board: public static int score() { first=true; // initially, looking for first yahtzee int sc = 0; // score so far count = new int[6]; int maxcount, maxloc, max2; // Row scorings: for (int row = 0; row < 5; row++) { /* DEBUG: System.out.println("Row "+row); */ Arrays.fill(count,0); maxcount = 0; maxloc=-1; max2 = 0; // Count number of 1s, 2s, ..., 6s in row: for (int i = 0; i < 5; i++) { int j = board[row][i]-1; count[j]++; if (count[j] > maxcount) { maxcount = count[j]; maxloc = j; } } // Using info about largest count, find second largest: for (int j = 0; j < 6; j++) { if (count[j] < maxcount && count[j] > max2) { max2 = count[j]; } } sc += update(maxcount,maxloc,max2); } // Do it all over again for columns: for (int col = 0; col < 5; col++) { /* DEBUG: System.out.println("Col "+col); */ Arrays.fill(count,0); maxcount = 0; maxloc=-1; max2 = 0; // Count number of 1s, 2s, ..., 6s in column: for (int i = 0; i < 5; i++) { int j = board[i][col]-1; count[j]++; if (count[j] > maxcount) { maxcount = count[j]; maxloc = j; } } // Using info about largest count, find second largest: for (int j = 0; j < 6; j++) { if (count[j] < maxcount && count[j] > max2) { max2 = count[j]; } } sc += update(maxcount,maxloc,max2); } // Finally, do it for each diagonal: /* DEBUG: System.out.println("Diag 1"); */ Arrays.fill(count,0); maxcount = 0; maxloc=-1; max2 = 0; // Count number of 1s, 2s, ..., 6s in diag 1: for (int i = 0; i < 5; i++) { int j = board[i][i]-1; count[j]++; if (count[j] > maxcount) { maxcount = count[j]; maxloc = j; } } // Using info about largest count, find second largest: for (int j = 0; j < 6; j++) { if (count[j] < maxcount && count[j] > max2) { max2 = count[j]; } } sc += update(maxcount,maxloc,max2); /* DEBUG: System.out.println("Diag 2"); */ Arrays.fill(count,0); maxcount = 0; maxloc=-1; max2 = 0; // Count number of 1s, 2s, ..., 6s in diag 1: for (int i = 0; i < 5; i++) { int j = board[i][4-i]-1; count[j]++; if (count[j] > maxcount) { maxcount = count[j]; maxloc = j; } } // Using info about largest count, find second largest: for (int j = 0; j < 6; j++) { if (count[j] < maxcount && count[j] > max2) { max2 = count[j]; } } sc += update(maxcount,maxloc,max2); return sc; } public static int update(int maxcount, int maxloc, int max2) { int sc = 0; // Check for yahtzee if (maxcount == 5) { sc += 50; if (first) first = false; else sc += 50; // extra 50 for more than one yahtzee //System.out.println("Yahtzee"); } else // no yahtzee, so check for straight: if (maxcount == 1 && (count[0]==0 || count[5]==0)) { sc += 40; //System.out.println("straight"); } else // check for small straight: if (count[2] > 0 && count[3] > 0 && ((count[0] > 0 && count[1] > 0) || (count[1] > 0 && count[4] > 0) || (count[4] > 0 && count[5] > 0))) { sc += 30; //System.out.println("small straight"); } else // check for full house: if (maxcount == 3 && max2 == 2) { sc += 25; //System.out.println("full house"); } else // check for 4 of a kind: if (maxcount == 4) { sc += 4*(maxloc+1); //System.out.println("Four of a kind--adding " + (4*(maxloc+1))); } else // check for 3 of a kind; we've already eliminated full house: if (maxcount == 3) { sc += 3*(maxloc+1); //System.out.println("Three of a kind--adding " + (3*(maxloc+1))); } return sc; } }