NEERC/kequiv/kequiv_petr.java

   1 import java.io.BufferedReader;
   2 import java.io.FileReader;
   3 import java.io.PrintWriter;
   4 import java.io.IOException;
   5 import java.util.*;
   6
   7 public class kequiv_petr implements Runnable {
   8     class Segment {
   9         long l;
  10         long r;
  11
  12         Segment(long l, long r) {
  13             this.l = l;
  14             this.r = r;
  15         }
  16
  17         @Override
  18         public boolean equals(Object o) {
  19             if (this == o) return true;
  20             if (o == null || getClass() != o.getClass()) return false;
  21
  22             Segment segment = (Segment) o;
  23
  24             if (l != segment.l) return false;
  25             if (r != segment.r) return false;
  26
  27             return true;
  28         }
  29
  30         @Override
  31         public int hashCode() {
  32             int result = (int) (l ^ (l >>> 32));
  33             result = 31 * result + (int) (r ^ (r >>> 32));
  34             return result;
  35         }
  36     }
  37
  38     private void solve() throws IOException {
  39         int n = nextInt();
  40         Segment[] segments = new Segment[n];
  41         for (int i = 0; i < n; ++i) {
  42             long l = nextLong();
  43             long r = nextLong();
  44             segments[i] = new Segment(l, r);
  45         }
  46         boolean[][] diff = new boolean[10][10];
  47         long p10 = 1;
  48         for (int pos = 0; pos <= 18; ++pos) {
  49             oneStep(segments, p10, diff);
  50             p10 *= 10;
  51         }
  52         boolean[] mark = new boolean[10];
  53         for (int i = 1; i < 10; ++i)
  54             if (!mark[i]) {
  55                 for (int j = 1; j < 10; ++j)
  56                     if (!diff[i][j]) {
  57                         mark[j] = true;
  58                         writer.print(j);
  59                     }
  60                 writer.println();
  61             }
  62     }
  63
  64     private void oneStep(Segment[] segments, long p10, boolean[][] diff) {
  65         Map<List<Segment>, List<Integer>> allDigits = new HashMap<List<Segment>, List<Integer>>();
  66         for (int digit = 1; digit < 10; ++digit) {
  67             List<Segment> cur = new ArrayList<Segment>();
  68             for (Segment s : segments) {
  69                 long nl = getNext(s.l, p10, digit);
  70                 long nr = getNext(s.r + 1, p10, digit) - 1;
  71                 if (nl <= nr) {
  72                     if (cur.size() > 0 && cur.get(cur.size() - 1).r >= nl - 1) {
  73                         cur.set(cur.size() - 1, new Segment(cur.get(cur.size() - 1).l, nr));
  74                     } else {
  75                         cur.add(new Segment(nl, nr));
  76                     }
  77                 }
  78             }
  79             List<Integer> list = allDigits.get(cur);
  80             if (list == null) {
  81                 list = new ArrayList<Integer>();
  82                 allDigits.put(cur, list);
  83             }
  84             list.add(digit);
  85         }
  86         for (List<Integer> l1 : allDigits.values())
  87             for (List<Integer> l2 : allDigits.values())
  88                 if (l1 != l2)
  89                     for (Integer a1 : l1)
  90                         for (Integer a2 : l2)
  91                             diff[a1][a2] = true;
  92     }
  93
  94     private long getNext(long l, long p10, int digit) {
  95         long cd = l / p10 % 10;
  96         if (cd == digit)
  97             return l / p10 / 10 * p10 + l % p10;
  98         else if (cd < digit)
  99             return l / p10 / 10 * p10;
 100         else
 101             return (l / p10 / 10 + 1) * p10;
 102     }
 103
 104
 105     public static void main(String[] args) throws InterruptedException {
 106         Thread thread = new Thread(new kequiv_petr());
 107         thread.start();
 108         thread.join();
 109     }
 110
 111     static final String TASK_ID = "kequiv";
 112     static final String IN_FILE = TASK_ID + ".in";
 113     static final String OUT_FILE = TASK_ID + ".out";
 114     BufferedReader reader;
 115     StringTokenizer tokenizer;
 116     PrintWriter writer;
 117
 118     public void run() {
 119         try {
 120             reader = new BufferedReader(new FileReader(IN_FILE));
 121             tokenizer = null;
 122             writer = new PrintWriter(OUT_FILE);
 123             solve();
 124             reader.close();
 125             writer.close();
 126         } catch (Exception e) {
 127             e.printStackTrace();
 128             System.exit(1);
 129         }
 130     }
 131
 132     int nextInt() throws IOException {
 133         return Integer.parseInt(nextToken());
 134     }
 135
 136     long nextLong() throws IOException {
 137         return Long.parseLong(nextToken());
 138     }
 139
 140     double nextDouble() throws IOException {
 141         return Double.parseDouble(nextToken());
 142     }
 143
 144     String nextToken() throws IOException {
 145         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
 146             tokenizer = new StringTokenizer(reader.readLine());
 147         }
 148         return tokenizer.nextToken();
 149     }
 150 }