NEERC/kequiv/kequiv_ia_vd.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 /**
   5  * @author Iskander Akishev
   6  * @author Vladimir Danilov
   7  */
   8 public class kequiv_ia_vd implements Runnable {
   9
  10         private static final String FILE_NAME = "kequiv";
  11
  12         public void run() {
  13                 try {
  14                         solve();
  15                 } catch (Throwable t) {
  16                         t.printStackTrace();
  17                         System.exit(1);
  18                 }
  19         }
  20
  21         private BufferedReader in;
  22         private PrintWriter out;
  23
  24         enum Type {
  25                 FULL, NORMAL
  26         }
  27
  28         private final Node FULL_NODE = new Node(Type.FULL);
  29
  30         class Node {
  31                 Node[] children;
  32                 Type type;
  33                 int classId = -1;
  34
  35                 Node(Type type) {
  36                         this.type = type;
  37                         children = new Node[10];
  38                 }
  39
  40                 @Override
  41                 public boolean equals(Object o) {
  42                         return hashCode() == o.hashCode();
  43                 }
  44
  45                 @Override
  46                 public int hashCode() {
  47                         if (classId == -1) {
  48                                 if (type == Type.FULL) {
  49                                         return -12354125;
  50                                 }
  51                                 classId = children != null ? Arrays.hashCode(children) : 0;
  52                         }
  53                         return classId;
  54                 }
  55
  56                 public int getClassId() {
  57                         return hashCode();
  58                 }
  59         }
  60
  61         private void solve() throws Exception {
  62                 in = new BufferedReader(new FileReader(FILE_NAME + ".in"));
  63                 out = new PrintWriter(new File(FILE_NAME + ".out"));
  64
  65                 Node root = new Node(Type.NORMAL);
  66                 int n = Integer.parseInt(in.readLine());
  67                 for (int i = 0; i < n; i++) {
  68                         StringTokenizer st = new StringTokenizer(in.readLine());
  69                         String a = readNumber(st);
  70                         String b = readNumber(st);
  71                         insert(root, a, b, 0);
  72                 }
  73
  74                 int[] col = new int[10];
  75                 for (int i = 1; i < 10; i++) {
  76                         col[i] = i;
  77                 }
  78                 for (int i = 1; i < 10; i++) {
  79                         for (int j = i + 1; j < 10; j++) {
  80                                 if (check(root, i, j)) {
  81                                         col[j] = col[i] = Math.min(col[j], col[i]);
  82                                 }
  83                         }
  84                 }
  85
  86                 for (int i = 1; i < 10; i++) {
  87                         if (col[i] == i) {
  88                                 for (int j = 0; j < 10; j++) {
  89                                         if (col[j] == col[i]) {
  90                                                 out.print(j);
  91                                         }
  92                                 }
  93                                 out.println();
  94                         }
  95                 }
  96
  97                 in.close();
  98                 out.close();
  99         }
 100
 101         private boolean check(Node r, int a, int b) {
 102                 if (r == null) {
 103                         return true;
 104                 }
 105                 if (r.type == Type.NORMAL) {
 106                         if (r.children[a] == null || r.children[b] == null) {
 107                                 if (r.children[a] != r.children[b]) {
 108                                         return false;
 109                                 }
 110                         } else if (r.children[a].getClassId() != r.children[b].getClassId()) {
 111                                 return false;
 112                         }
 113                         for (Node ch : r.children) {
 114                                 if (!check(ch, a, b)) {
 115                                         return false;
 116                                 }
 117                         }
 118                 }
 119                 return true;
 120         }
 121
 122         private Node insert(Node root, String a, String b, int h) {
 123                 if (root == null) {
 124                         root = new Node(Type.NORMAL);
 125                 }
 126
 127                 if (h == M + 1) {
 128                         return FULL_NODE;
 129                 }
 130                 if (charsOnly(a, h, '0') && charsOnly(b, h, '9')) {
 131                         return FULL_NODE;
 132                 }
 133                 int ca = a.charAt(h) - '0';
 134                 int cb = b.charAt(h) - '0';
 135
 136                 if (ca == cb) {
 137                         root.children[ca] = insert(root.children[ca], a, b, h + 1);
 138                 } else {
 139                         root.children[ca] = insert(root.children[ca], a, generate(a, h, '9'), h + 1);
 140                         for (int i = ca + 1; i < cb; i++) {
 141                                 root.children[i] = FULL_NODE;
 142                         }
 143                         root.children[cb] = insert(root.children[cb], generate(b, h, '0'), b, h + 1);
 144                 }
 145
 146                 return root;
 147         }
 148
 149         private String generate(String s, int h, char c) {
 150                 return s.substring(0, h + 1) + chars[c - '0'][M - (h + 1)];
 151         }
 152
 153         private boolean charsOnly(String s, int h, char c) {
 154                 for (int i = h; i < M; i++) {
 155                         if (s.charAt(i) != c)
 156                                 return false;
 157                 }
 158                 return true;
 159         }
 160
 161         final static int M = 19;
 162         final static String[][] chars;
 163         static {
 164                 chars = new String[10][M + 1];
 165                 for (int i = 0; i < 10; i++) {
 166                         chars[i][0] = "";
 167                         for (int j = 1; j < M + 1; j++) {
 168                                 chars[i][j] = chars[i][j - 1] + i;
 169                         }
 170                 }
 171         }
 172
 173         private String readNumber(StringTokenizer st) {
 174                 String res = st.nextToken();
 175                 return chars[0][M - res.length()] + res;
 176         }
 177
 178         public static void main(String[] args) {
 179                 new Thread(new kequiv_ia_vd()).start();
 180         }
 181 }