c501: 旅行者_九國遊歷記<7> 小紫去鷹國
Tags : 旅行者
Accepted rate : 14人/17人 ( 82% ) [非即時]
評分方式:
Strictly

最近更新 : 2018-09-14 11:49

Content

運動健將小紫到了鷹國,這裡月月都有運動盛事,讓小紫一來,全身肌肉都沸騰起來。

 

“來對地方了”小紫說”竟然來到運動的天堂,就去找找有什麼特別的運動吧!”

 

於是她開始了兩天一夜不吃不喝不睡的尋找行程,所看到了,不是熟悉的種類,就是太多人參與,使得他進不去的,直到他找到”六立方球”,他覺得很有意思,想要來試試看,收集三種不同顏色的球各一顆為一組,每次進行這項運動的組數個不同,這些球長在一條長達1000公尺的筆直道路,她必須親自收集,球不均勻散布道路上,小紫想讓收集區間越短越好,越快收集完,她就可以花更多時間在進行這項運動上,她有一台平板顯示所有球的位置,於是她開始計算……

Input

第一行有數字T代表有T組測資,接下來每組測資第一行有兩個數字N,M代表這條路有N顆球,她必須所集M組,第2N+1行各有兩個整數d,c代表距離和顏色。

對於40%的測資,T<=10,d<=1000

(0<T<=1000,3<=N<=1000,0<M<=100,0<=d<=10000000,1<=c<=3)

Output

根據每一筆測資,輸出最短的收集區間,如果沒辦法收集成所需組數,請輸出”QQ”(不含引號)。

Sample Input
2
5 1
1 1
10 2
6 3
99 1
8 2
5 1
1 1
10 2
6 1
99 1
8 2
Sample Output
7
QQ
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (40%): 1.0s , <1M
不公開 測資點#1 (60%): 1.0s , <1M
不公開 測資點#2 (0%): 1.0s , <1M
不公開 測資點#3 (0%): 1.0s , <1M
Hint :
Tags:
旅行者
出處:
107學年度板橋高中校內資訊學科能力競賽 [管理者:
snail (蝸牛)
]


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