荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: Minimal coverage
发信站: 荔园晨风BBS站 (Sun Mar 28 11:45:47 2004), 站内信件
Minimal coverage
Time Limit: 1.0 second
Memory Limit: 1 000 КБ
Given set of line segments [Li , Ri] with integer coordinates of their end
points. Your task is to find the minimal subset of the given set which
covers segment [0,M] completely (M is a positive integer).
Input
First line of the input contains number M (1 <= M <= 5000). Subsequent lines
of input contain pairs of numbers Li and Ri (abs(Li), abs(Ri) <= 50000).
Each pair is placed on separate line. Numbers in the pair are separated with
space(s). List of pairs is ended with pair of integers "0 0". i <= 100000
Output
Your program should print in the first line of output the power of minimal
subset of segments which covers segment [0, M]. The list of segments of
covering subset must follow. Format of the list must be the same as
described in input with exception that ending pair "0 0" should not be
printed. Segments should be printed in increasing order of their left end
point coordinate.
If there is no covering subset then print "No solution" to output.
Sample Input
1
-1 0
-5 –3
2 5
0 0
Sample Output
1
-1 0
0 1
0 0
--
Long long ago,there is a hero stand at the edge of the land.......
▁▁
▕天外▏
▕飞仙▏
▔▔
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.157]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店