NEERC/kequiv/kequiv_ia_vd_memlimit.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_memlimit 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                 EMPTY, FULL, NORMAL
  26         }
  27
  28         final Map<NodeInfo, Integer> map = new HashMap<NodeInfo, Integer>();
  29         final NodeInfo EMPTY_INFO = new NodeInfo(null);
  30         final NodeInfo FULL_INFO = new NodeInfo(null);
  31         int EMPTY_CLASS_ID = getClassId(EMPTY_INFO);
  32         int FULL_CLASS_ID = getClassId(FULL_INFO);
  33
  34         int getClassId(NodeInfo ni) {
  35                 Integer res = map.get(ni);
  36                 if (res == null) {
  37                         map.put(ni, res = map.size());
  38                 }
  39                 return res;
  40         }
  41
  42         class NodeInfo {
  43                 int[] classes;
  44
  45                 NodeInfo(int[] classes) {
  46                         this.classes = classes;
  47                 }
  48
  49                 @Override
  50                 public boolean equals(Object o) {
  51                         NodeInfo nodeInfo = (NodeInfo)o;
  52                         if (this == EMPTY_INFO || this == FULL_INFO) {
  53                                 return this == o;
  54                         }
  55                         if (o == EMPTY_INFO || o == FULL_INFO) {
  56                                 return false;
  57                         }
  58                         if (!Arrays.equals(classes, nodeInfo.classes)) return false;
  59                         return true;
  60                 }
  61
  62                 @Override
  63                 public int hashCode() {
  64                         return classes != null ? Arrays.hashCode(classes) : 0;
  65                 }
  66         }
  67
  68         class Node {
  69                 Node[] children;
  70                 Type type;
  71                 int classId = -1;
  72
  73                 Node(Type type) {
  74                         this.type = type;
  75                 }
  76
  77                 public int getClassId() {
  78                         if (classId == -1) {
  79                                 if (type == Type.EMPTY) {
  80                                         return EMPTY_CLASS_ID;
  81                                 } else if (type == Type.FULL) {
  82                                         return FULL_CLASS_ID;
  83                                 }
  84                                 int[] c = new int[10];
  85                                 for (int i = 0; i < 10; i++) {
  86                                         c[i] = children[i].getClassId();
  87                                 }
  88                                 classId = kequiv_ia_vd_memlimit.this.getClassId(new NodeInfo(c));
  89                         }
  90                         return classId;
  91                 }
  92         }
  93
  94         private void solve() throws Exception {
  95                 in = new BufferedReader(new FileReader(FILE_NAME + ".in"));
  96                 out = new PrintWriter(new File(FILE_NAME + ".out"));
  97
  98                 Node root = new Node(Type.EMPTY);
  99                 int n = Integer.parseInt(in.readLine());
 100                 for (int i = 0; i < n; i++) {
 101                         StringTokenizer st = new StringTokenizer(in.readLine());
 102                         String a = readNumber(st);
 103                         String b = readNumber(st);
 104                         insert(root, a, b, 0);
 105                 }
 106
 107                 int[] col = new int[10];
 108                 for (int i = 1; i < 10; i++) {
 109                         col[i] = i;
 110                 }
 111                 for (int i = 1; i < 10; i++) {
 112                         for (int j = i + 1; j < 10; j++) {
 113                                 if (check(root, i, j)) {
 114                                         col[j] = col[i] = Math.min(col[j], col[i]);
 115                                 }
 116                         }
 117                 }
 118
 119                 for (int i = 1; i < 10; i++) {
 120                         if (col[i] == i) {
 121                                 for (int j = 0; j < 10; j++) {
 122                                         if (col[j] == col[i]) {
 123                                                 out.print(j);
 124                                         }
 125                                 }
 126                                 out.println();
 127                         }
 128                 }
 129
 130                 in.close();
 131                 out.close();
 132         }
 133
 134         private boolean check(Node r, int a, int b) {
 135                 if (r.type == Type.NORMAL) {
 136                         if (r.children[a].getClassId() != r.children[b].getClassId()) {
 137                                 return false;
 138                         }
 139                         for (Node ch : r.children) {
 140                                 if (!check(ch, a, b)) {
 141                                         return false;
 142                                 }
 143                         }
 144                 }
 145                 return true;
 146         }
 147
 148         private void insert(Node root, String a, String b, int h) {
 149                 if (h == M + 1) {
 150                         root.type = Type.FULL;
 151                         root.children = null;
 152                         return;
 153                 }
 154                 if (charsOnly(a, h, '0') && charsOnly(b, h, '9')) {
 155                         root.type = Type.FULL;
 156                         root.children = null;
 157                         return;
 158                 }
 159                 int ca = a.charAt(h) - '0';
 160                 int cb = b.charAt(h) - '0';
 161
 162                 if (root.type == Type.EMPTY) {
 163                         root.type = Type.NORMAL;
 164                         root.children = new Node[10];
 165                         for (int i = 0; i < 10; i++) {
 166                                 root.children[i] = new Node(Type.EMPTY);
 167                         }
 168                 }
 169                 if (ca == cb) {
 170                         insert(root.children[ca], a, b, h + 1);
 171                 } else {
 172                         insert(root.children[ca], a, generate(a, h, '9'), h + 1);
 173                         for (int i = ca + 1; i < cb; i++) {
 174                                 root.children[i] = new Node(Type.FULL);
 175                         }
 176                         insert(root.children[cb], generate(b, h, '0'), b, h + 1);
 177                 }
 178         }
 179
 180         private String generate(String s, int h, char c) {
 181                 return s.substring(0, h + 1) + chars[c - '0'][M - (h + 1)];
 182         }
 183
 184         private boolean charsOnly(String s, int h, char c) {
 185                 for (int i = h; i < M; i++) {
 186                         if (s.charAt(i) != c)
 187                                 return false;
 188                 }
 189                 return true;
 190         }
 191
 192         final static int M = 19;
 193         final static String[][] chars;
 194         static {
 195                 chars = new String[10][M + 1];
 196                 for (int i = 0; i < 10; i++) {
 197                         chars[i][0] = "";
 198                         for (int j = 1; j < M + 1; j++) {
 199                                 chars[i][j] = chars[i][j - 1] + i;
 200                         }
 201                 }
 202         }
 203
 204         private String readNumber(StringTokenizer st) {
 205                 String res = st.nextToken();
 206                 return chars[0][M - res.length()] + res;
 207         }
 208
 209         public static void main(String[] args) {
 210                 new Thread(new kequiv_ia_vd_memlimit()).start();
 211         }
 212 }