NEERC/kequiv/kequiv_md.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class kequiv_md {
   5         private static String fileName = kequiv_md.class.getSimpleName().replaceFirst("_.*", "");
   6         private static String inputFileName = fileName + ".in";
   7         private static String outputFileName = fileName + ".out";
   8         private static Scanner in;
   9         private static PrintWriter out;
  10         private final static int TEN = 10;
  11
  12         class Intervals {
  13                 ArrayList<Long> low = new ArrayList<Long>();
  14                 ArrayList<Long> high = new ArrayList<Long>();
  15                 int hash = 0;
  16
  17                 public void add(long lo, long hi) {
  18                         if (lo < hi) {
  19                                 low.add(lo);
  20                                 high.add(hi);
  21                         }
  22                 }
  23
  24                 public Intervals setDigit(long ten, int d) {
  25                         Intervals that = new Intervals();
  26                         for (int i = 0; i < low.size(); i++) {
  27                                 that.add(above(low.get(i), ten, d), above(high.get(i), ten, d));
  28                         }
  29                         return that.normalize();
  30                 }
  31
  32                 private Intervals normalize() {
  33                         if (low.isEmpty()) {
  34                                 return this;
  35                         }
  36                         Intervals that = new Intervals();
  37                         that.low.add(low.get(0));
  38                         for (int i = 0; i < low.size() - 1; i++) {
  39                                 if (high.get(i) < low.get(i + 1)) {
  40                                         that.high.add(high.get(i));
  41                                         that.low.add(low.get(i + 1));
  42                                 }
  43                         }
  44                         that.high.add(high.get(high.size() - 1));
  45                         return that;
  46                 }
  47
  48                 @Override
  49                 public boolean equals(Object obj) {
  50                         Intervals that = (Intervals) obj;
  51                         return low.equals(that.low) && high.equals(that.high);
  52                 }
  53
  54                 @Override
  55                 public int hashCode() {
  56                         if (hash == 0) {
  57                                 hash = low.hashCode() * 179 + high.hashCode();
  58                         }
  59                         return hash;
  60                 }
  61         }
  62
  63         public Long above(long n, long ten, int d) {
  64                 long a = n / ten;
  65                 int c = (int) (a % 10);
  66                 a /= 10;
  67                 long b = n % ten;
  68                 if (c < d) {
  69                         return a * ten;
  70                 }
  71                 if (c > d) {
  72                         return (a + 1) * ten;
  73                 }
  74                 return a * ten + b;
  75         }
  76
  77         public void run() {
  78                 Intervals a = new Intervals();
  79                 int n = in.nextInt();
  80                 for (int i = 0; i < n; i++) {
  81                         a.add(in.nextLong(), in.nextLong() + 1);
  82                 }
  83
  84                 boolean[][] differ = new boolean[TEN][TEN];
  85                 for (long ten = 1; ten < a.high.get(a.high.size() - 1) && ten > 0; ten *= TEN) {
  86                         int[] val = new int[TEN];
  87                         HashMap<Intervals, Integer> results = new HashMap<Intervals, Integer>();
  88                         for (int d = 1; d < TEN; d++) {
  89                                 Intervals b = a.setDigit(ten, d);
  90                                 Integer v = results.get(b);
  91                                 if (v == null) {
  92                                         v = results.size();
  93                                         results.put(b, v);
  94                                 }
  95                                 val[d] = v;
  96                                 for (int e = 1; e < d; e++) {
  97                                         if (val[d] != val[e]) {
  98                                                 differ[e][d] = true;
  99                                         }
 100                                 }
 101                         }
 102                 }
 103
 104                 boolean[] printed = new boolean[TEN];
 105                 for (int d = 1; d < TEN; d++) {
 106                         if (printed[d]) {
 107                                 continue;
 108                         }
 109                         for (int e = d; e < TEN; e++) {
 110                                 if (!differ[d][e]) {
 111                                         out.print(e);
 112                                         printed[e] = true;
 113                                 }
 114                         }
 115                         out.println();
 116                 }
 117         }
 118
 119         public static void main(String[] args) throws IOException {
 120                 Locale.setDefault(Locale.US);
 121                 in = new Scanner(new FileReader(inputFileName));
 122                 out = new PrintWriter(outputFileName);
 123                 new kequiv_md().run();
 124                 in.close();
 125                 out.close();
 126         }
 127 }