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: Minimal coverage
Description 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 No solution Hint Huge input,scanf is recommended.
Sample input #2 1 -1 0 0 1 0 0 Sample output #2 1 0 1 Source |

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

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator