Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: K-equivalence
Description 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 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. Input 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 <= 10 ^{18}. Also, for i [2..n]: ai >= b(i-1) + 2.Output 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. Sample Input Sample Input #1: 1 1 566 Sample Input #2: 1 30 75 Sample Output Sample Output #1: 1234 5 6 789 Sample Output #2: 12 345 6 7 89 Source |

[Submit] [Go Back] [Status] [Discuss]

Any problem, Please Contact Administrator