NEERC/kequiv/kequiv_re.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 /**
   5  * Solution for NEERC'2009 Problem K: K-Equivalence
   6  * This solution checks correctness of the input.
   7  * @author Roman Elizarov
   8  */
   9 public class kequiv_re {
  10         static final boolean DEBUG = false;
  11
  12         public static void main(String[] args) throws Exception {
  13                 new kequiv_re().go();
  14         }
  15
  16         void go() throws Exception {
  17                 read();
  18                 solve();
  19                 write();
  20         }
  21
  22         int n;
  23         long[] a;
  24         long[] b;
  25
  26         void read() throws Exception {
  27                 Scanner in = new Scanner(new File("kequiv.in"));
  28                 in.useLocale(Locale.US);
  29                 n = in.nextInt();
  30                 in.nextLine();
  31                 assert n >= 1 && n <= 10000;
  32                 a = new long[n];
  33                 b = new long[n];
  34                 for (int i = 0; i < n; i++) {
  35                         a[i] = in.nextLong();
  36                         b[i] = in.nextLong();
  37                         in.nextLine();
  38                         assert a[i] >= 1 && a[i] <= b[i] && b[i] <= 1000000000000000000L;
  39                         assert i == 0 || a[i] >= b[i - 1] + 2;
  40                 }
  41                 in.close();
  42         }
  43
  44
  45         long[] p10 = new long[19];
  46         long[] s = new long[1];
  47         int[] t = new int[1];
  48         int m;
  49
  50         int cc;
  51         int[] cn = new int[11];
  52
  53         void solve() {
  54                 p10[0] = 1;
  55                 for (int i = 1; i < p10.length; i++) {
  56                     p10[i] = p10[i - 1] * 10;
  57                 }
  58                 for (int i = 0; i < n; i++) {
  59                         long a = this.a[i];
  60                         long b = this.b[i] + 1;
  61                         while (a < b) {
  62                                 int t = 0;
  63                                 while (t + 1 < p10.length && a + p10[t + 1] <= b && a % p10[t + 1] == 0)
  64                                         t++;
  65                                 append(a, t);
  66                                 a += p10[t];
  67                         }
  68                 }
  69                 for (int p = 1; p < 10; p++) {
  70                         if (cn[p] == 0) {
  71                                 cc++;
  72                                 mark(p);
  73                         }
  74                 }
  75         }
  76
  77         void append(long s0, int t0) {
  78                 int capacity = s.length;
  79                 if (m >= capacity) {
  80                         s = Arrays.copyOf(s, capacity * 2);
  81                         t = Arrays.copyOf(t, capacity * 2);
  82                 }
  83                 s[m] = s0;
  84                 t[m] = t0;
  85                 m++;
  86                 if (DEBUG)
  87                         System.out.println(s0 + " - " + (s0 + p10[t0] - 1));
  88         }
  89
  90         void mark(int p) {
  91                 cn[p] = cc;
  92                 for (int q = 1; q < 10; q++) {
  93                         if (cn[q] == 0 && equiv(p, q))
  94                                 mark(q);
  95                 }
  96         }
  97
  98         private boolean equiv(int p, int q) {
  99                 for (int i = 0; i < m; i++) {
 100                         long s = this.s[i];
 101                         int t = this.t[i];
 102                         for (int u = t; u <= 18; u++) {
 103                             if (p10[u] > s)
 104                                     break;
 105                         int d = (int)(s / p10[u] % 10);
 106                                 long ss = s;
 107                                 if (d == p)
 108                                         ss += p10[u] * (q - p);
 109                                 else if (d == q)
 110                                         ss += p10[u] * (p - q);
 111                                 else
 112                                         continue;
 113                                 if (u == 18)
 114                                         return false; // any shift by multiple of 10^18 is always out of range
 115                                 int j = Arrays.binarySearch(a, 0, n, ss);
 116                                 if (j < 0)
 117                                         j = -j - 2;
 118                                 if (j < 0 || j >= n || ss + p10[t] - 1 > b[j])
 119                                         return false; // out of range
 120                     }
 121                 }
 122                 return true;
 123         }
 124
 125         void write() throws Exception {
 126                 PrintWriter out = new PrintWriter("kequiv.out");
 127                 boolean[] w = new boolean[11];
 128                 for (int p = 1; p < 10; p++) {
 129                         if (!w[p]) {
 130                                 for (int q = p; q < 10; q++) {
 131                                         if (cn[q] == cn[p]) {
 132                                                 w[q] = true;
 133                                                 out.print(q);
 134                                         }
 135                                 }
 136                                 out.println();
 137                         }
 138                 }
 139                 out.close();
 140         }
 141
 142 //----------------- just for validation ------------------
 143
 144         /**
 145          * Strict scanner to veryfy 100% correspondence between input files and input file format specification.
 146          * It is a drop-in replacement for {@link java.util.Scanner} that could be added to a soulution source
 147          * (cut-and-paste) without breaking its ability to work with {@link java.util.Scanner}.
 148          */
 149         public class Scanner {
 150                 private final BufferedReader in;
 151                 private String line = "";
 152                 private int pos;
 153                 private int lineNo;
 154                 private boolean localeset;
 155
 156                 public Scanner(File source) throws FileNotFoundException {
 157                         in = new BufferedReader(new FileReader(source));
 158                         nextLine();
 159                 }
 160
 161                 public void close() {
 162                         assert line == null : "Extra data at the end of file";
 163                         try {
 164                                 in.close();
 165                         } catch (IOException e) {
 166                                 throw new AssertionError("Failed to close with " + e);
 167                         }
 168                 }
 169
 170                 public void nextLine() {
 171                         assert line != null : "EOF";
 172                         assert pos == line.length() : "Extra characters on line " + lineNo;
 173                         try {
 174                                 line = in.readLine();
 175                         } catch (IOException e) {
 176                                 throw new AssertionError("Failed to read line with " + e);
 177                         }
 178                         pos = 0;
 179                         lineNo++;
 180                 }
 181
 182                 public String next() {
 183                         assert line != null : "EOF";
 184                         assert line.length() > 0 : "Empty line " + lineNo;
 185                         if (pos == 0)
 186                                 assert line.charAt(0) > ' ' : "Line " + lineNo + " starts with whitespace";
 187                         else {
 188                                 assert pos < line.length() : "Line " + lineNo + " is over";
 189                                 assert line.charAt(pos) == ' ' : "Wrong whitespace on line " + lineNo;
 190                                 pos++;
 191                                 assert pos < line.length() : "Line " + lineNo + " is over";
 192                                 assert line.charAt(0) > ' ' : "Line " + lineNo + " has double whitespace";
 193                         }
 194                         StringBuilder sb = new StringBuilder();
 195                         while (pos < line.length() && line.charAt(pos) > ' ')
 196                                 sb.append(line.charAt(pos++));
 197                         return sb.toString();
 198                 }
 199
 200                 public int nextInt() {
 201                         String s = next();
 202                         assert s.length() == 1 || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
 203                         assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
 204                         try {
 205                                 return Integer.parseInt(s);
 206                         } catch (NumberFormatException e) {
 207                                 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
 208                         }
 209                 }
 210
 211                 public long nextLong() {
 212                         String s = next();
 213                         assert s.length() == 1 || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
 214                         assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
 215                         try {
 216                                 return Long.parseLong(s);
 217                         } catch (NumberFormatException e) {
 218                                 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
 219                         }
 220                 }
 221
 222                 public double nextDouble() {
 223                         assert localeset : "Locale must be set with useLocale(Locale.US)";
 224                         String s = next();
 225                         assert s.length() == 1 || s.startsWith("0.") || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
 226                         assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
 227                         try {
 228                                 return Double.parseDouble(s);
 229                         } catch (NumberFormatException e) {
 230                                 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
 231                         }
 232                 }
 233
 234                 public void useLocale(Locale locale) {
 235                         assert locale == Locale.US;
 236                         localeset = true;
 237                 }
 238         }
 239 }