首页 > 代码库 > POJ 3872 Nescafe模拟赛 Laser
POJ 3872 Nescafe模拟赛 Laser
传送门：http://poj.org/problem?id=3872
K-equivalence
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 117 | Accepted: 32 |
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.
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.
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 <= 1018. Also, for i [2..n]: ai >= b(i-1) + 2.
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 >= 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.
Output all the equivalence classes of digits 1 to 9, one at a line, sorted lexicographically.
Sample Input
Sample Input #1:11 566Sample Input #2:130 75Sample Output
Sample Output #1:123456789Sample Output #2:123456789Source
Northeastern Europe 2009
POJ 3872 Nescafe模拟赛 Laser
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。