This is a solution to the FairAndSquare problem asked in the qualification round of Google Code Jam-2013. Please read the problem statement very carefully as the correctness of solution depends heavily on how you understand and interpret the problem statement.
We present here two solutions to the problem one for the small input and the other for the large input -1. The solution for large input of the problem is kind-of inverted approach from the straightforward one taken for the small input solution. This is also in accordance to the second approach as described in the Code Jam Analysis of the problem.
Solution for Small input:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
//package com.google.codejam; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.regex.Matcher; import java.util.regex.Pattern; public class FairAndSquare { private File inputFile = new File("C-small-attempt0.in"); private File outputFile = new File("C-small-attempt0.out"); FileReader reader; BufferedReader bufReader; FileWriter writer; BufferedWriter buffWriter; private int numCases; /** * @param args */ public static void main(String[] args) { FairAndSquare t = new FairAndSquare(); t.generateOutput(); } private void generateOutput() { try { reader = new FileReader(inputFile); writer = new FileWriter(outputFile); bufReader = new BufferedReader(reader); buffWriter = new BufferedWriter(writer); String caseLine = bufReader.readLine(); numCases = Integer.parseInt(caseLine); Pattern p = Pattern.compile("\\.0*([1-9])+"); int positives = 0; for (int i = 1; i <= numCases; i++) { caseLine = bufReader.readLine(); positives = 0; String[] limits = caseLine.split(" "); int minNum = Integer.parseInt(limits[0]); int maxNum = Integer.parseInt(limits[1]); for (int num = minNum; num <= maxNum; num++) { Double sqrt = Math.sqrt(num); String str = sqrt.toString(); Matcher m = p.matcher(str); if (m.find()) { // System.out.println(num + "pattern found"); } else { str = str.substring(0, str.indexOf(".")); if (IsPalindrome(num + "") && IsPalindrome(str)) { // System.out.println(num + "inside"); positives++; } } } // System.out.println("Case #" + i + ": " + positives); buffWriter.write("Case #" + i + ": " + positives); buffWriter.newLine(); // this.initialize(caseLine); } // buffWriter.write("Case #" + caseNum + ": " + // valueMap.get(nextValDiff) + " " + (i + 1)); // buffWriter.newLine(); buffWriter.close(); writer.close(); bufReader.close(); reader.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } boolean IsPalindrome(String s) { int stringLength = s.length(); int halfStringLength = stringLength; for (int i = 0; i < halfStringLength; i++) { if (s.charAt(i) != s.charAt(stringLength - 1 - i)) return false; } return true; } } |
Solution Large Input – 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
package com.google.codejam; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.ArrayList; public class FairAndSquare { private File inputFile = new File("C-large-1.in"); private File outputFile = new File("C-large-1.out"); FileReader reader; BufferedReader bufReader; FileWriter writer; BufferedWriter buffWriter; private int numCases; /** * @param args */ public static void main(String[] args) { FairAndSquare t = new FairAndSquare(); t.generateOutput(); } private void generateOutput() { try { reader = new FileReader(inputFile); writer = new FileWriter(outputFile); bufReader = new BufferedReader(reader); buffWriter = new BufferedWriter(writer); String caseLine = bufReader.readLine(); numCases = Integer.parseInt(caseLine); ArrayList<Long> fns = new ArrayList<Long>(); long minNum = 1; long maxNum = (long) Math.floor(Math.sqrt(100000000000000L)); for (long num = 1; num <= maxNum; num++) { if (IsPalindrome(num + "")) { long square = num * num; if (IsPalindrome(square + "")) { // System.out.println(num + " " + square + " "); fns.add(square); } } } int positives = 0; for (int i = 1; i <= numCases; i++) { caseLine = bufReader.readLine(); positives = 0; String[] limits = caseLine.split(" "); minNum = Long.parseLong(limits[0]); maxNum = Long.parseLong(limits[1]); for (long num : fns) { if (num >= minNum && num <= maxNum) { positives++; } } // System.out.println("Case #" + i + ": " + positives); buffWriter.write("Case #" + i + ": " + positives); buffWriter.newLine(); } // buffWriter.write("Case #" + caseNum + ": " + // valueMap.get(nextValDiff) + " " + (i + 1)); // buffWriter.newLine(); buffWriter.close(); writer.close(); bufReader.close(); reader.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } boolean IsPalindrome(String s) { int stringLength = s.length(); int halfStringLength = stringLength; for (int i = 0; i < halfStringLength; i++) { if (s.charAt(i) != s.charAt(stringLength - 1 - i)) return false; } return true; } } |