NEERC/database/database_re.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 /**
   5  * Solution for NEERC'2009 Problem D: Database
   6  * This solution checks correctness of the input.
   7  * @author Roman Elizarov
   8  */
   9 public class database_re {
  10
  11         public static void main(String[] args) throws Exception {
  12                 new database_re().go();
  13         }
  14
  15         void go() throws Exception {
  16                 read();
  17                 solve();
  18                 write();
  19         }
  20
  21         int n;
  22         int m;
  23         List<List<String>> rows = new ArrayList<List<String>>();
  24
  25         void read() throws Exception {
  26                 Scanner in = new Scanner(new File("database.in"));
  27                 in.useLocale(Locale.US);
  28                 n = in.nextInt();
  29                 m = in.nextInt();
  30                 String rest = in.nextLine();
  31                 assert rest.equals("");
  32                 assert n >= 1 && n <= 10000;
  33                 assert m >= 1 && m <= 10;
  34                 for (int i = 0; i < n; i++) {
  35                         String line = in.nextLine();
  36                         assert line.length() <= 80;
  37                         List<String> row = Arrays.asList(line.split(","));
  38                         assert row.size() == m;
  39                         for (int j = 0; j < m; j++) {
  40                                 String s = row.get(j);
  41                                 assert s.trim().equals(s);
  42                                 assert s.length() > 0;
  43                                 for (int k = 0; k < s.length(); k++) {
  44                                         char c = s.charAt(k);
  45                                         assert c >= 32 && c <= 126 && c != 44;
  46                                 }
  47                         }
  48                         rows.add(row);
  49                 }
  50                 in.close();
  51         }
  52
  53         boolean found;
  54         int r1;
  55         int r2;
  56         int c1;
  57         int c2;
  58
  59         void solve() {
  60                 for (int i = 0; i < m; i++) {
  61                     for (int j = i + 1; j < m; j++) {
  62                                 checkRowPair(i, j);
  63                             if (found)
  64                                         return;
  65                     }
  66                 }
  67         }
  68
  69         static class Pair {
  70                 String s1;
  71                 String s2;
  72
  73                 Pair(String s1, String s2) {
  74                         this.s1 = s1;
  75                         this.s2 = s2;
  76                 }
  77
  78                 @Override
  79                 public boolean equals(Object o) {
  80                         if (this == o)
  81                                 return true;
  82                         if (!(o instanceof Pair))
  83                                 return false;
  84
  85                         Pair pair = (Pair)o;
  86
  87                         if (!s1.equals(pair.s1))
  88                                 return false;
  89                         if (!s2.equals(pair.s2))
  90                                 return false;
  91
  92                         return true;
  93                 }
  94
  95                 @Override
  96                 public int hashCode() {
  97                         int result = s1.hashCode();
  98                         result = 31 * result + s2.hashCode();
  99                         return result;
 100                 }
 101         }
 102
 103         private void checkRowPair(int i, int j) {
 104                 Map<Pair, Integer> vals = new HashMap<Pair, Integer>();
 105                 for (int k = 0; k < n; k++) {
 106                         List<String> row = rows.get(k);
 107                         Integer old = vals.put(new Pair(row.get(i), row.get(j)), k);
 108                         if (old != null) {
 109                                 r1 = old;
 110                                 r2 = k;
 111                                 c1 = i;
 112                                 c2 = j;
 113                                 found = true;
 114                                 return;
 115                         }
 116                 }
 117         }
 118
 119         void write() throws Exception {
 120                 PrintWriter out = new PrintWriter("database.out");
 121                 if (!found)
 122                         out.println("YES");
 123                 else {
 124                         out.println("NO");
 125                         out.printf("%d %d%n", r1 + 1, r2 + 1);
 126                         out.printf("%d %d%n", c1 + 1, c2 + 1);
 127                 }
 128                 out.close();
 129         }
 130
 131 //----------------- just for validation ------------------
 132
 133         /**
 134          * Strict scanner to veryfy 100% correspondence between input files and input file format specification.
 135          * It is a drop-in replacement for {@link java.util.Scanner} that could be added to a soulution source
 136          * (cut-and-paste) without breaking its ability to work with {@link java.util.Scanner}.
 137          */
 138         public class Scanner {
 139                 private final BufferedReader in;
 140                 private String line = "";
 141                 private int pos;
 142                 private int lineNo;
 143                 private boolean localeset;
 144
 145                 public Scanner(File source) throws FileNotFoundException {
 146                         in = new BufferedReader(new FileReader(source));
 147                         nextLine();
 148                 }
 149
 150                 public void close() {
 151                         assert line == null : "Extra data at the end of file";
 152                         try {
 153                                 in.close();
 154                         } catch (IOException e) {
 155                                 throw new AssertionError("Failed to close with " + e);
 156                         }
 157                 }
 158
 159                 public String nextLine() {
 160                         assert line != null : "EOF";
 161                         String result = line.substring(pos);
 162                         try {
 163                                 line = in.readLine();
 164                         } catch (IOException e) {
 165                                 throw new AssertionError("Failed to read line with " + e);
 166                         }
 167                         pos = 0;
 168                         lineNo++;
 169                         return result;
 170                 }
 171
 172
 173                 public String next() {
 174                         assert line != null : "EOF";
 175                         assert line.length() > 0 : "Empty line " + lineNo;
 176                         if (pos == 0)
 177                                 assert line.charAt(0) > ' ' : "Line " + lineNo + " starts with whitespace";
 178                         else {
 179                                 assert pos < line.length() : "Line " + lineNo + " is over";
 180                                 assert line.charAt(pos) == ' ' : "Wrong whitespace on line " + lineNo;
 181                                 pos++;
 182                                 assert pos < line.length() : "Line " + lineNo + " is over";
 183                                 assert line.charAt(0) > ' ' : "Line " + lineNo + " has double whitespace";
 184                         }
 185                         StringBuilder sb = new StringBuilder();
 186                         while (pos < line.length() && line.charAt(pos) > ' ')
 187                                 sb.append(line.charAt(pos++));
 188                         return sb.toString();
 189                 }
 190
 191                 public int nextInt() {
 192                         String s = next();
 193                         assert s.length() == 1 || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
 194                         assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
 195                         try {
 196                                 return Integer.parseInt(s);
 197                         } catch (NumberFormatException e) {
 198                                 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
 199                         }
 200                 }
 201
 202                 public double nextDouble() {
 203                         assert localeset : "Locale must be set with useLocale(Locale.US)";
 204                         String s = next();
 205                         assert s.length() == 1 || s.startsWith("0.") || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
 206                         assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
 207                         try {
 208                                 return Double.parseDouble(s);
 209                         } catch (NumberFormatException e) {
 210                                 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
 211                         }
 212                 }
 213
 214                 public void useLocale(Locale locale) {
 215                         assert locale == Locale.US;
 216                         localeset = true;
 217                 }
 218         }
 219 }