NEERC/kequiv/kequiv_al_trivial.java

   1 import java.util.*;
   2 import java.io.*;
   3
   4 public class kequiv_al_trivial {
   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
  23   static boolean [][] G;
  24   static int [] C;
  25   static int cc;
  26
  27
  28   static void dfs (int x) {
  29     C[x] = cc;
  30     for (int j = 1; j <= 9; j++)
  31       if (C[j] == 0 && G[x][j])
  32         dfs (j);
  33   }
  34
  35   public static void main (String args []) throws Exception {
  36     BufferedReader in = new BufferedReader (new FileReader ("kequiv.in"));
  37     PrintWriter out = new PrintWriter ("kequiv.out");
  38     int n = Integer.parseInt (in.readLine ());
  39     rangeLong (n, 1, MaxN);
  40
  41     long [] a = new long [n], b = new long [n];
  42     long last = -1;
  43
  44     for (int i = 0; i < n; i++) {
  45       StringTokenizer tok = new StringTokenizer (in.readLine ());
  46       String as = tok.nextToken ();
  47       String bs = tok.nextToken ();
  48       a[i] = rangeLong (as, last + 2, MaxAB);
  49       b[i] = rangeLong (bs, a[i], MaxAB);
  50       if (tok.hasMoreTokens ()) throw new Exception ("EOL expected");
  51     }
  52
  53     if (in.ready ()) throw new Exception ("EOF expected");
  54
  55     G = new boolean [10][10];
  56
  57     for (int i = 1; i <= 9; i++)
  58       for (int j = 1; j <= 9; j++)
  59         G[i][j] = true;
  60
  61     for (int i = 0; i < n; i++) {
  62       for (long x = a[i]; x <= b[i]; x++) {
  63         char [] c = ("" + x).toCharArray ();
  64         for (int p = 0; p < c.length; p++) {
  65           if (c[p] != '0') {
  66             char sav = c[p];
  67             for (int d = 1; d <= 9; d++) {
  68               c[p] = (char)(d + '0');
  69               long y = Long.parseLong (new String (c));
  70               boolean found = false;
  71               for (int j = 0; j < n; j++) {
  72                 if (a[j] <= y && y <= b[j]) {
  73                   found = true;
  74                 }
  75               }
  76               if (!found) {
  77                 if (G[sav - '0'][d]) {
  78                   //System.out.println (x + " -> " + y + " blocks " + sav + " -> " + d);
  79                 }
  80                 G[sav - '0'][d] = false;
  81                 G[d][sav - '0'] = false;
  82               }
  83             }
  84             c[p] = sav;
  85           }
  86         }
  87       }
  88     }
  89
  90     C = new int [10];
  91     cc = 0;
  92
  93     for (int i = 1; i <= 9; i++) {
  94       if (C[i] == 0) {
  95         ++cc;
  96         dfs (i);
  97       }
  98     }
  99
 100     for (int i = 1; i <= cc; i++) {
 101       for (int j = 1; j <= 9; j++) {
 102         if (C[j] == i) {
 103           out.print (j);
 104         }
 105       }
 106       out.println ();
 107     }
 108     out.close ();
 109   }
 110 }