시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 9 | 5 | 5 | 83.333% |
Consider a set K of positive integers.
Let p and q be two non-zero decimal digits. Call them K-equivalent if the following condition applies:
For every n ∈ K, if you replace one digit p with q or one digit q with p in the decimal notation of n then the resulting number will be an element of K.
For example, when K is the set of integers divisible by 3, the digits 1, 4, and 7 are K-equivalent. Indeed, replacing a 1 with a 4 in the decimal notation of a number never changes its divisibility by 3.
It can be seen that K-equivalence is an equivalence relation (it is reflexive, symmetric and transitive).
You are given a finite set K in form of a union of disjoint finite intervals of positive integers.
Your task is to find the equivalence classes of digits 1 to 9.
The first line contains n, the number of intervals composing the set K (1 ≤ n ≤ 10 000).
Each of the next n lines contains two positive integers ai and bi that describe the interval [ai, bi] (i. e. the set of positive integers between ai and bi, inclusive), where 1 ≤ ai ≤ bi ≤ 1018. Also, for i ∈ [2..n]: ai ≥ bi−1 + 2.
Represent each equivalence class as a concatenation of its elements, in ascending order.
Output all the equivalence classes of digits 1 to 9, one at a line, sorted lexicographically.
1 1 566
1234 5 6 789
1 30 75
12 345 6 7 89
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2009 K번