NEERC/kequiv/kequiv_al_slow.java

   1 import java.util.*;
   2 import java.io.*;
   3
   4 public class kequiv_al_slow {
   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     BufferedReader in = new BufferedReader (new FileReader ("kequiv.in"));
  41     PrintWriter out = new PrintWriter ("kequiv.out");
  42     int n = Integer.parseInt (in.readLine ());
  43     rangeLong (n, 1, MaxN);
  44
  45     long [] T = new long [PL];
  46     T[PL - 1] = 1;
  47     for (int i = PL - 2; i >= 0; i--) T[i] = T[i + 1] * 10;
  48
  49     long [] a = new long [n], b = new long [n];
  50     char [][] ac = new char [n][], bc = new char [n][];
  51     long last = -1;
  52
  53     for (int i = 0; i < n; i++) {
  54       StringTokenizer tok = new StringTokenizer (in.readLine ());
  55       String as = tok.nextToken ();
  56       String bs = tok.nextToken ();
  57       a[i] = rangeLong (as, last + 2, MaxAB);
  58       b[i] = rangeLong (bs, a[i], MaxAB);
  59       char [] d = new char [PL - as.length ()];
  60       Arrays.fill (d, '0');
  61       ac[i] = (new String (d) + as).toCharArray ();
  62       d = new char [PL - bs.length ()];
  63       Arrays.fill (d, '0');
  64       bc[i] = (new String (d) + bs).toCharArray ();
  65       last = b[i];
  66       if (tok.hasMoreTokens ()) throw new Exception ("EOL expected");
  67     }
  68
  69     if (in.ready ()) throw new Exception ("EOF expected");
  70
  71     long [][][] ast = new long[n][10][PL], bfn = new long [n][10][PL];
  72     long [][][] aln = new long[n][10][PL], bln = new long [n][10][PL];
  73
  74     for (int i = 0; i < n; i++)
  75       for (int d1 = 1; d1 <= 9; d1++)
  76         for (int p = 0; p < PL; p++) {
  77           char [] cur = ac[i].clone ();
  78           //System.out.println (cur);
  79           long fR = T[p] - myLong (new String (Arrays.copyOfRange (ac[i], p + 1, PL)));
  80           if (cur[p] == d1 + '0') {
  81             ast[i][d1][p] = a[i];
  82             aln[i][d1][p] = Math.min (fR, b[i] - a[i] + 1);
  83           } else {
  84             ast[i][d1][p] = a[i] + fR + (digdist (cur[p] - '0', d1) - 1) * T[p];
  85             aln[i][d1][p] = Math.min (T[p], b[i] - ast[i][d1][p] + 1);
  86           }
  87           //System.out.println (i + " " + d1 + " " + " " + p + ": " + fR + " " + ast[i][d1][p]);
  88
  89           cur = bc[i].clone ();
  90           fR = myLong (new String (Arrays.copyOfRange (bc[i], p + 1, PL))) + 1;
  91           if (cur[p] == d1 + '0') {
  92             bfn[i][d1][p] = b[i];
  93             bln[i][d1][p] = Math.min (fR, b[i] - a[i] + 1);
  94           } else {
  95             bfn[i][d1][p] = b[i] - fR - (digdist (d1, cur[p] - '0') - 1) * T[p];
  96             bln[i][d1][p] = Math.min (T[p], bfn[i][d1][p] - a[i] + 1);
  97           }
  98         }
  99
 100
 101     G = new boolean [10][10];
 102
 103     for (int i = 1; i <= 9; i++)
 104       for (int j = 1; j <= 9; j++)
 105         G[i][j] = true;
 106
 107     System.out.println (".1");
 108
 109     for (int d1 = 1; d1 <= 9; d1++)
 110       for (int d2 = 1; d2 <= 9; d2++) {
 111         for (int p = 0; p < PL; p++) {
 112           int j = 0;
 113           for (int i = 0; i < n; i++) {
 114             if (aln[i][d1][p] > 0) {
 115               //check A interval
 116               long tofind = ast[i][d1][p] + (d2 - d1) * T[p];
 117               //System.out.println ("tofind = " + tofind);
 118               while (j < n && b[j] < tofind) ++j;
 119               //System.out.println ("j = " + j + ", a[j] = " + a[j] + ", b[j] = " + b[j]);
 120               if (j == n || a[j] > tofind)  {
 121                 if (G[d1][d2]) {
 122                   //System.out.println ("(" + p + "): " + ast[i][d1][p] + " -> " + bfn[i][d1][p] + " blocks " + d1 + " -> " + d2);
 123                 }
 124                 G[d1][d2] = false;
 125                 G[d2][d1] = false;
 126                 break;
 127               }
 128               long toend = bfn[i][d1][p] + (d2 - d1) * T[p];
 129               //System.out.println ("toend = " + toend);
 130               while (j < n && b[j] < toend) {
 131                 int oj = j;
 132                 do {
 133                   ++j;
 134                 } while (j < n && aln[j][d2][p] <= 0);
 135                 if (j >= n) {
 136                   break;
 137                 }
 138                 /*if (ast[j][d2][p] - bfn[oj][d2][p] < 9 * T[p] + 1) {
 139                   throw new Exception ("bug detected (" + j + ", " + d2 + ", " + p + "): " + ast[j][d2][p] + " " + bfn[oj][d2][p]);
 140                 }*/
 141                 if (ast[j][d2][p] - bfn[oj][d2][p] != 9 * T[p] + 1) {
 142                   j = n;
 143                   break;
 144                 }
 145               }
 146               if (j == n) {
 147                 if (G[d1][d2]) {
 148                   //System.out.println ("(" + p + "): " + ast[i][d1][p] + " -> " + bfn[i][d1][p] + " blocks " + d1 + " -> " + d2);
 149                 }
 150                 G[d1][d2] = false;
 151                 G[d2][d1] = false;
 152                 break;
 153               }
 154               if (a[j] > toend) {
 155                 throw new RuntimeException ("bug detected");
 156               }
 157             }
 158           }
 159         }
 160       }
 161
 162     System.out.println (".2");
 163
 164     C = new int [10];
 165     cc = 0;
 166
 167     for (int i = 1; i <= 9; i++) {
 168       if (C[i] == 0) {
 169         ++cc;
 170         dfs (i);
 171       }
 172     }
 173
 174     for (int i = 1; i <= cc; i++) {
 175       for (int j = 1; j <= 9; j++) {
 176         if (C[j] == i) {
 177           out.print (j);
 178         }
 179       }
 180       out.println ();
 181     }
 182     out.close ();
 183   }
 184 }