Back to Category
d240: [12.06] A - Cut The Sticks

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 2 Times | Submit :74 Times | Clicks : 539
Accepted : 2 Users | Submit : 3 Users | Accepted rate : 67%
Time Limit :3000 ms | Memory Limit : 64000 KBytes
Update : 2012-10-29 17:20


Temmo have N sticks to cut. All of the sticks are placed parallel with the axis. The left side of the i-th stick is at the coordinate li, and the right side of that is at the coordinate ri. For convenience you can treat these sticks as segments.
Temmo needs to make C cuts. The coordinate of each cut ci must be integer, and between the left most coordinate of li and the right most coordinate of ri (inclusive). And the distance between each pair of cuts must not be less than G. He wants to make the work easier, so he wants to cut the least sticks in these C cuts. The i-th stick is cut by the j-th cut if li ≤ cj ≤ ri. Denote wi as the number of sticks would be cut in the i-th cut, can you tell him the minimum sum of all wi

Technical Speci cation

  •  1 ≤ N ≤ 104
  •  1 ≤ G,C ≤ 10
  •  1 ≤ li, ri ≤ 212
  •  All of the numbers are integers. 


There are at most 100 test cases in the input. Each test case starts with
three numbers N, G, C in a line. Then followed by N lines, each of these
lines contains two numbers li and ri.


For each test case output the minimum sum of wi.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3 1 2
2 5
3 6
7 9

Sample Output :


Hint :

click here to download the problem solving hint

Author :

  Solve it!   Status Forum

50828. rabbit125
(352ms, 916KB, 1739B)

Program running time may be affected by various factors. Check server system environment information here