NEERC/kequiv/kequiv_rs.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class kequiv_rs implements Runnable {
   5     private BufferedReader in;
   6     private PrintWriter out;
   7
   8     private void check(boolean expr, String msg) {
   9         if (!expr) {
  10             throw new Error(msg);
  11         }
  12     }
  13
  14     private void checkBounds(int n, int low, int hi, String nStr) {
  15         check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  16     }
  17
  18     private long[] a, b;
  19     private long[] ten;
  20     private long[] x, y;
  21     private long[] intersect1X, intersect1Y;
  22     private long[] intersect2X, intersect2Y;
  23     private int n, m;
  24
  25     private long[][] aTen, bTen;
  26
  27     private boolean examine(int d1, int d2, int k, long a, long b) {
  28         long x1 = d1 * ten[k - 1];
  29         long y1 = (d1 + 1) * ten[k - 1] - 1;
  30
  31         long x2 = d2 * ten[k - 1];
  32         long y2 = (d2 + 1) * ten[k - 1] - 1;
  33
  34         boolean contains1 = (a <= x1 && y1 <= b);
  35         boolean contains2 = (a <= x2 && y2 <= b);
  36         boolean intersects1 = !(b < x1 || a > y1);
  37         boolean intersects2 = !(b < x2 || a > y2);
  38
  39         if (intersects1 && !contains1) {
  40             return false;
  41         }
  42         if (intersects2 && !contains2) {
  43             return false;
  44         }
  45
  46         return contains1 == contains2;
  47     }
  48
  49     private boolean testEQ(int d1, int d2) {
  50         for (int k = 1; k <= 18; k++) {
  51             m = 0;
  52             for (int i = 0; i < n; i++) {
  53                 long left = aTen[k][i];
  54                 long right = bTen[k][i];
  55                 if (left < right) {
  56                     x[m] = a[i];
  57                     y[m] = left * ten[k] + ten[k] - 1;
  58                     m++;
  59
  60                     x[m] = right * ten[k];
  61                     y[m] = b[i];
  62                     m++;
  63                 } else {
  64                     x[m] = a[i];
  65                     y[m] = b[i];
  66                     m++;
  67                 }
  68             }
  69             long x1 = d1 * ten[k - 1];
  70             long y1 = (d1 + 1) * ten[k - 1] - 1;
  71
  72             long x2 = d2 * ten[k - 1];
  73             long y2 = (d2 + 1) * ten[k - 1] - 1;
  74             for (int i = 0; i < m; i++) {
  75                 long curLeft = x[i] - x[i] % ten[k];
  76                 long curRight = curLeft + ten[k] - 1;
  77                 int hi = m - 1;
  78                 for (int j = i; j < m; j++) {
  79                     if (x[j] > curRight) {
  80                         hi = j - 1;
  81                         break;
  82                     }
  83                 }
  84
  85                 int count1 = 0;
  86                 int count2 = 0;
  87                 for (int j = i; j <= hi; j++) {
  88                     long from = x[j] % ten[k];
  89                     long to = y[j] % ten[k];
  90
  91                     long f1 = Math.max(from, x1);
  92                     long t1 = Math.min(to, y1);
  93                     if (f1 <= t1) {
  94                         intersect1X[count1] = f1 - x1;
  95                         intersect1Y[count1++] = t1 - x1;
  96                     }
  97                     long f2 = Math.max(from, x2);
  98                     long t2 = Math.min(to, y2);
  99                     if (f2 <= t2) {
 100                         intersect2X[count2] = f2 - x2;
 101                         intersect2Y[count2++] = t2 - x2;
 102                     }
 103                 }
 104
 105                 if (count1 != count2) {
 106                     return false;
 107                 }
 108                 for (int j = 0; j < count1; j++) {
 109                     if (intersect1X[j] != intersect2X[j]) {
 110                         return false;
 111                     }
 112                     if (intersect1Y[j] != intersect2Y[j]) {
 113                         return false;
 114                     }
 115                 }
 116
 117                 i = hi;
 118             }
 119         }
 120         return true;
 121     }
 122
 123     private void solve() throws IOException {
 124         n = Integer.parseInt(in.readLine());
 125         checkBounds(n, 1, 10000, "n");
 126         a = new long[n];
 127         b = new long[n];
 128         for (int i = 0; i < n; i++) {
 129             StringTokenizer st = new StringTokenizer(in.readLine());
 130             a[i] = Long.parseLong(st.nextToken());
 131             b[i] = Long.parseLong(st.nextToken());
 132             check((1 <= a[i]) && (a[i] <= b[i]) && (b[i] <= 1000000000000000000L), "invalid interval");
 133         }
 134         for (int i = 0; i + 1 < n; i++) {
 135             check(b[i] + 2 <= a[i + 1], "touching or overlaping intervals");
 136         }
 137
 138         ten = new long[19];
 139         ten[0] = 1;
 140         for (int i = 1; i < ten.length; i++) {
 141             ten[i] = 10 * ten[i - 1];
 142         }
 143
 144         aTen = new long[19][n];
 145         bTen = new long[19][n];
 146         for (int k = 0; k <= 18; k++) {
 147             for (int i = 0; i < n; i++) {
 148                 aTen[k][i] = a[i] / ten[k];
 149                 bTen[k][i] = b[i] / ten[k];
 150             }
 151         }
 152
 153         x = new long[2 * n];
 154         y = new long[2 * n];
 155         intersect1X = new long[2 * n];
 156         intersect1Y = new long[2 * n];
 157         intersect2X = new long[2 * n];
 158         intersect2Y = new long[2 * n];
 159
 160         testEQ(4, 5);
 161
 162         boolean[][] eq = new boolean[10][10];
 163         for (int u = 1; u < 10; u++) {
 164             eq[u][u] = true;
 165             for (int v = u + 1; v < 10; v++) {
 166                 if ((b[n - 1] == ten[18]) && (u == 1)) {
 167                     eq[u][v] = false;
 168                     continue;
 169                 }
 170                 eq[u][v] = testEQ(u, v);
 171             }
 172         }
 173
 174         boolean[] mark = new boolean[10];
 175         for (int i = 1; i < 10; i++) {
 176             if (mark[i]) {
 177                 continue;
 178             }
 179             for (int j = i; j < 10; j++) {
 180                 if (eq[i][j]) {
 181                     mark[j] = true;
 182                     out.print(j);
 183                 }
 184             }
 185             out.println();
 186         }
 187     }
 188
 189     public static void main(String[] args) {
 190         new Thread(new kequiv_rs()).start();
 191     }
 192
 193     public void run() {
 194         String problem = getClass().getName().split("_")[0];
 195         try {
 196             in = new BufferedReader(new FileReader(new File(problem + ".in")));
 197             out = new PrintWriter(new File(problem + ".out"));
 198             solve();
 199             in.close();
 200             out.close();
 201         } catch (IOException e) {
 202             e.printStackTrace();
 203             System.exit(1);
 204         }
 205     }
 206 }