4 public class kequiv_rs
implements Runnable
{
5 private BufferedReader in
;
6 private PrintWriter out
;
8 private void check(boolean expr
, String msg
) {
14 private void checkBounds(int n
, int low
, int hi
, String nStr
) {
15 check((low
<= n
) && (n
<= hi
), nStr
+ " is not in [" + low
+ ", " + hi
+ "]");
21 private long[] intersect1X
, intersect1Y
;
22 private long[] intersect2X
, intersect2Y
;
25 private long[][] aTen
, bTen
;
27 private boolean examine(int d1
, int d2
, int k
, long a
, long b
) {
28 long x1
= d1
* ten
[k
- 1];
29 long y1
= (d1
+ 1) * ten
[k
- 1] - 1;
31 long x2
= d2
* ten
[k
- 1];
32 long y2
= (d2
+ 1) * ten
[k
- 1] - 1;
34 boolean contains1
= (a
<= x1
&& y1
<= b
);
35 boolean contains2
= (a
<= x2
&& y2
<= b
);
36 boolean intersects1
= !(b
< x1
|| a
> y1
);
37 boolean intersects2
= !(b
< x2
|| a
> y2
);
39 if (intersects1
&& !contains1
) {
42 if (intersects2
&& !contains2
) {
46 return contains1
== contains2
;
49 private boolean testEQ(int d1
, int d2
) {
50 for (int k
= 1; k
<= 18; k
++) {
52 for (int i
= 0; i
< n
; i
++) {
53 long left
= aTen
[k
][i
];
54 long right
= bTen
[k
][i
];
57 y
[m
] = left
* ten
[k
] + ten
[k
] - 1;
60 x
[m
] = right
* ten
[k
];
69 long x1
= d1
* ten
[k
- 1];
70 long y1
= (d1
+ 1) * ten
[k
- 1] - 1;
72 long x2
= d2
* ten
[k
- 1];
73 long y2
= (d2
+ 1) * ten
[k
- 1] - 1;
74 for (int i
= 0; i
< m
; i
++) {
75 long curLeft
= x
[i
] - x
[i
] % ten
[k
];
76 long curRight
= curLeft
+ ten
[k
] - 1;
78 for (int j
= i
; j
< m
; j
++) {
79 if (x
[j
] > curRight
) {
87 for (int j
= i
; j
<= hi
; j
++) {
88 long from
= x
[j
] % ten
[k
];
89 long to
= y
[j
] % ten
[k
];
91 long f1
= Math
.max(from
, x1
);
92 long t1
= Math
.min(to
, y1
);
94 intersect1X
[count1
] = f1
- x1
;
95 intersect1Y
[count1
++] = t1
- x1
;
97 long f2
= Math
.max(from
, x2
);
98 long t2
= Math
.min(to
, y2
);
100 intersect2X
[count2
] = f2
- x2
;
101 intersect2Y
[count2
++] = t2
- x2
;
105 if (count1
!= count2
) {
108 for (int j
= 0; j
< count1
; j
++) {
109 if (intersect1X
[j
] != intersect2X
[j
]) {
112 if (intersect1Y
[j
] != intersect2Y
[j
]) {
123 private void solve() throws IOException
{
124 n
= Integer
.parseInt(in
.readLine());
125 checkBounds(n
, 1, 10000, "n");
128 for (int i
= 0; i
< n
; i
++) {
129 StringTokenizer st
= new StringTokenizer(in
.readLine());
130 a
[i
] = Long
.parseLong(st
.nextToken());
131 b
[i
] = Long
.parseLong(st
.nextToken());
132 check((1 <= a
[i
]) && (a
[i
] <= b
[i
]) && (b
[i
] <= 1000000000000000000L), "invalid interval");
134 for (int i
= 0; i
+ 1 < n
; i
++) {
135 check(b
[i
] + 2 <= a
[i
+ 1], "touching or overlaping intervals");
140 for (int i
= 1; i
< ten
.length
; i
++) {
141 ten
[i
] = 10 * ten
[i
- 1];
144 aTen
= new long[19][n
];
145 bTen
= new long[19][n
];
146 for (int k
= 0; k
<= 18; k
++) {
147 for (int i
= 0; i
< n
; i
++) {
148 aTen
[k
][i
] = a
[i
] / ten
[k
];
149 bTen
[k
][i
] = b
[i
] / ten
[k
];
155 intersect1X
= new long[2 * n
];
156 intersect1Y
= new long[2 * n
];
157 intersect2X
= new long[2 * n
];
158 intersect2Y
= new long[2 * n
];
162 boolean[][] eq
= new boolean[10][10];
163 for (int u
= 1; u
< 10; u
++) {
165 for (int v
= u
+ 1; v
< 10; v
++) {
166 if ((b
[n
- 1] == ten
[18]) && (u
== 1)) {
170 eq
[u
][v
] = testEQ(u
, v
);
174 boolean[] mark
= new boolean[10];
175 for (int i
= 1; i
< 10; i
++) {
179 for (int j
= i
; j
< 10; j
++) {
189 public static void main(String
[] args
) {
190 new Thread(new kequiv_rs()).start();
194 String problem
= getClass().getName().split("_")[0];
196 in
= new BufferedReader(new FileReader(new File(problem
+ ".in")));
197 out
= new PrintWriter(new File(problem
+ ".out"));
201 } catch (IOException e
) {