I lazily figured out weather a given nubmer was good enough or not by trying all combinations. I’m sure there’s a better (greedy) way to do this that involves less work. Greedy doesn’t always work, but though so be careful! I messed up twice by trying a greedy strategy and gave up when I got tired of finding something that has no counterexamples.<\/p>\n
\r\nimport java.io.PrintWriter;\r\nimport java.util.Arrays;\r\nimport java.util.Scanner;\r\n\r\n\/**\r\n * \r\n * @author Sanchit M. Bhatnagar\r\n * @see http:\/\/uhunt.felix-halim.net\/id\/74004\r\n * \r\n *\/\r\npublic class P12247 {\r\n\r\n public static void main(String[] args) {\r\n Scanner sc = new Scanner(System.in);\r\n PrintWriter out = new PrintWriter(System.out);\r\n\r\n while (sc.hasNext()) {\r\n int[] princess = new int[] { sc.nextInt(), sc.nextInt(), sc.nextInt() };\r\n if (princess[0] == 0)\r\n break;\r\n int[] prince = new int[] { -1, sc.nextInt(), sc.nextInt() };\r\n out.println(check(princess, prince));\r\n }\r\n\r\n out.close();\r\n sc.close();\r\n }\r\n\r\n \/\/ Cheating\r\n private static int[][] perm = { new int[] { 0, 1, 2 }, new int[] { 0, 2, 1 }, new int[] { 1, 0, 2 }, new int[] { 1, 2, 0 }, new int[] { 2, 0, 1 }, new int[] { 2, 1, 0 } };\r\n\r\n private static int check(int[] princess, int[] prince) {\r\n int[] tmpPrincess = Arrays.copyOf(princess, princess.length);\r\n int[] tmpPrince = null;\r\n int min = 1;\r\n boolean found = false;\r\n for (int i = min; !found && i <= 52; i++) {\r\n tmpPrince = Arrays.copyOf(prince, prince.length);\r\n tmpPrince[0] = i;\r\n if (i != tmpPrincess[0] && i != tmpPrincess[1] && i != tmpPrincess[2] && i != tmpPrince[1] && i != tmpPrince[2]) {\r\n min = i;\r\n \/\/ Try to lose\r\n int count = 0;\r\n for (int j = 0; count == 0 && j < perm.length; j++) {\r\n int subCount = 0;\r\n for (int k = 0; k < 3; k++) {\r\n if (tmpPrince[perm[j][k]] > tmpPrincess[k]) {\r\n subCount++;\r\n }\r\n }\r\n if (subCount < 2)\r\n count++;\r\n }\r\n if (count == 0)\r\n found = true;\r\n }\r\n }\r\n if (!found) {\r\n return -1;\r\n } else {\r\n return min;\r\n }\r\n }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"I lazily figured out weather a given nubmer was good enough or not by trying all combinations. I’m sure there’s a better (greedy) way to do this that involves less work. Greedy doesn’t always work, but though so be careful! I messed up twice by trying a greedy strategy and gave up when I got … Continue reading UVA 12247 – Jollo<\/span>