a014: 夾娃娃
Tags : BIT ST
Accepted rate : 54人/98人 ( 55% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-04-04 18:33

Content

現在在 1D 空間內夾娃娃,知道娃娃的位置,而這個遊戲很不公平

只要是在夾娃娃機的夾子範圍內,都可以夾起來,這簡直太不太平了

對於不會計算的小光,簡直是不公平的遊戲,請你幫忙解決這不公平的遊戲

 

遊戲規則:

假設現在夾娃娃機可以看成一個直線座標系,

夾娃娃機的機身範圍 X∈[0,+∞)

裡面有 N 個娃娃,

娃娃分布範圍 X[1,100000]

而每一個娃娃都位在 X1 [A,B]

若夾子寬度為 Y ,夾子的左端坐標為 C C ∈ N+

則夾子可以夾起 X2[C, C+Y] 這個範圍內的娃娃,

只要 X1 X2 ,則娃娃可以被夾起,

Y , A , B  ∈ N+

Input

有多筆測資

每組的第一行有兩個整數 N  Y  ( 1 ≦ N Y ≦ 3,0000 )
接下來會有 N 行,每行上有兩個正整數 A B ( 1 ≦ A ≦ B ≦ 10,0000 )

Output

請輸出最佳的夾取地點的個數(有幾個 C 值可以使夾起的娃娃最多)

以及可以夾到的最多的娃娃個數

Sample Input
5 4
1 3
2 5
3 6
2 6
5 7
5 4
1 3
2 5
3 6
2 5 
5 7
Sample Output
1 3
2 3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (19%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (30%): 1.0s , <1M
公開 測資點#3 (30%): 1.0s , <10M
公開 測資點#4 (1%): 1.0s , <1M
Hint :
Tags:
BIT ST
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」