NEERC/kequiv/kequiv_al.java

   1 import java.util.*;
   2 import java.io.*;
   3
   4 public class kequiv_al {
   5   static final int MaxN = 10000;
   6   static final long MaxAB = (long)1e18;
   7   static final int PL = 19;
   8
   9   static long rangeLong (long x, long a, long b) {
  10     if (x < a || x > b) throw new RuntimeException (x + " is not in range " + a + ".." + b);
  11     return x;
  12   }
  13
  14   static long rangeLong (String s, long a, long b) {
  15     return rangeLong (Long.parseLong (s), a, b);
  16   }
  17
  18   static long myLong (String s) {
  19     if (s.length () == 0) return 0; else return Long.parseLong (s);
  20   }
  21
  22   static int digdist (int d1, int d2) {
  23     if (d2 > d1) return d2 - d1; else return d2 - d1 + 10;
  24   }
  25
  26   static boolean [][] G;
  27   static int [] C;
  28   static int cc;
  29
  30
  31   static void dfs (int x) {
  32     C[x] = cc;
  33     for (int j = 1; j <= 9; j++)
  34       if (C[j] == 0 && G[x][j])
  35         dfs (j);
  36   }
  37
  38
  39   public static void main (String args []) throws Exception {
  40     long s = System.currentTimeMillis ();
  41     BufferedReader in = new BufferedReader (new FileReader ("kequiv.in"));
  42     PrintWriter out = new PrintWriter ("kequiv.out");
  43     int n = Integer.parseInt (in.readLine ());
  44     rangeLong (n, 1, MaxN);
  45
  46     long [] T = new long [PL];
  47     T[PL - 1] = 1;
  48     for (int i = PL - 2; i >= 0; i--) T[i] = T[i + 1] * 10;
  49
  50     long [] a = new long [n], b = new long [n];
  51     char [][] ac = new char [n][], bc = new char [n][];
  52     long last = -1;
  53
  54     for (int i = 0; i < n; i++) {
  55       StringTokenizer tok = new StringTokenizer (in.readLine ());
  56       String as = tok.nextToken ();
  57       String bs = tok.nextToken ();
  58       a[i] = rangeLong (as, last + 2, MaxAB);
  59       b[i] = rangeLong (bs, a[i], MaxAB);
  60       char [] d = new char [PL - as.length ()];
  61       Arrays.fill (d, '0');
  62       ac[i] = (new String (d) + as).toCharArray ();
  63       d = new char [PL - bs.length ()];
  64       Arrays.fill (d, '0');
  65       bc[i] = (new String (d) + bs).toCharArray ();
  66       last = b[i];
  67       if (tok.hasMoreTokens ()) throw new Exception ("EOL expected");
  68     }
  69
  70     if (in.ready ()) throw new Exception ("EOF expected");
  71
  72     System.out.println ("input: " + (System.currentTimeMillis () - s));
  73
  74     long [][][] ast = new long[n][10][PL], bfn = new long [n][10][PL];
  75     long [][][] aln = new long[n][10][PL], bln = new long [n][10][PL];
  76
  77     long [][] atl = new long[n][PL + 1], btl = new long [n][PL + 1];
  78     for (int i = 0; i < n; i++)
  79       for (int j = PL - 1; j >= 0; j--) {
  80         atl[i][j] = atl[i][j + 1] + (ac[i][j] - '0') * T[j];
  81         btl[i][j] = btl[i][j + 1] + (bc[i][j] - '0') * T[j];
  82       }
  83
  84
  85     for (int i = 0; i < n; i++)
  86       for (int d1 = 1; d1 <= 9; d1++)
  87         for (int p = 0; p < PL; p++) {
  88           //System.out.println (cur);
  89           long fR = T[p] - atl[i][p + 1];
  90           if (ac[i][p] == d1 + '0') {
  91             ast[i][d1][p] = a[i];
  92             aln[i][d1][p] = Math.min (fR, b[i] - a[i] + 1);
  93           } else {
  94             ast[i][d1][p] = a[i] + fR + (digdist (ac[i][p] - '0', d1) - 1) * T[p];
  95             aln[i][d1][p] = Math.min (T[p], b[i] - ast[i][d1][p] + 1);
  96           }
  97           //System.out.println (i + " " + d1 + " " + " " + p + ": " + fR + " " + ast[i][d1][p]);
  98
  99           fR = btl[i][p + 1] + 1;
 100           if (bc[i][p] == d1 + '0') {
 101             bfn[i][d1][p] = b[i];
 102             bln[i][d1][p] = Math.min (fR, b[i] - a[i] + 1);
 103           } else {
 104             bfn[i][d1][p] = b[i] - fR - (digdist (d1, bc[i][p] - '0') - 1) * T[p];
 105             bln[i][d1][p] = Math.min (T[p], bfn[i][d1][p] - a[i] + 1);
 106           }
 107         }
 108
 109
 110     System.out.println ("prepare: " + (System.currentTimeMillis () - s));
 111
 112     G = new boolean [10][10];
 113
 114     for (int i = 1; i <= 9; i++)
 115       for (int j = 1; j <= 9; j++)
 116         G[i][j] = true;
 117
 118
 119     for (int d1 = 1; d1 <= 9; d1++)
 120       for (int d2 = 1; d2 <= 9; d2++) {
 121         for (int p = 0; p < PL; p++) {
 122           int j = 0;
 123           for (int i = 0; i < n; i++) {
 124             if (aln[i][d1][p] > 0) {
 125               //check A interval
 126               long tofind = ast[i][d1][p] + (d2 - d1) * T[p];
 127               //System.out.println ("tofind = " + tofind);
 128               while (j < n && b[j] < tofind) ++j;
 129               //System.out.println ("j = " + j + ", a[j] = " + a[j] + ", b[j] = " + b[j]);
 130               if (j == n || a[j] > tofind)  {
 131                 if (G[d1][d2]) {
 132                   //System.out.println ("(" + p + "): " + ast[i][d1][p] + " -> " + bfn[i][d1][p] + " blocks " + d1 + " -> " + d2);
 133                 }
 134                 G[d1][d2] = false;
 135                 G[d2][d1] = false;
 136                 break;
 137               }
 138               long toend = bfn[i][d1][p] + (d2 - d1) * T[p];
 139               //System.out.println ("toend = " + toend);
 140               while (j < n && b[j] < toend) {
 141                 int oj = j;
 142                 do {
 143                   ++j;
 144                 } while (j < n && aln[j][d2][p] <= 0);
 145                 if (j >= n) {
 146                   break;
 147                 }
 148                 /*if (ast[j][d2][p] - bfn[oj][d2][p] < 9 * T[p] + 1) {
 149                   throw new Exception ("bug detected (" + j + ", " + d2 + ", " + p + "): " + ast[j][d2][p] + " " + bfn[oj][d2][p]);
 150                 }*/
 151                 if (ast[j][d2][p] - bfn[oj][d2][p] != 9 * T[p] + 1) {
 152                   j = n;
 153                   break;
 154                 }
 155               }
 156               if (j == n) {
 157                 //if (G[d1][d2]) {
 158                   //System.out.println ("(" + p + "): " + ast[i][d1][p] + " -> " + bfn[i][d1][p] + " blocks " + d1 + " -> " + d2);
 159                 //}
 160                 G[d1][d2] = false;
 161                 G[d2][d1] = false;
 162                 break;
 163               }
 164               if (a[j] > toend) {
 165                 throw new RuntimeException ("bug detected");
 166               }
 167             }
 168           }
 169         }
 170       }
 171
 172     C = new int [10];
 173     cc = 0;
 174
 175     for (int i = 1; i <= 9; i++) {
 176       if (C[i] == 0) {
 177         ++cc;
 178         dfs (i);
 179       }
 180     }
 181
 182     System.out.println ("complete: " + (System.currentTimeMillis () - s));
 183     for (int i = 1; i <= cc; i++) {
 184       for (int j = 1; j <= 9; j++) {
 185         if (C[j] == i) {
 186           out.print (j);
 187         }
 188       }
 189       out.println ();
 190     }
 191     out.close ();
 192   }
 193 }