「我與小明不相見已有二年餘了,我最不能忘記的是他的雙腿。(雖然他根本沒有)」
光陰荏苒,你如今是一位御用新聞記者,專門替國王烏龜的電視台採訪各式各樣的新聞。
還記得TIOJ 1623--國王烏龜的接駁車嗎?大意就是國王烏龜開放死老百姓烏龜們去覲見國王,
舉國上下無不歡聲雷動,一時之間各個直達皇宮接駁車的站牌前都排滿了烏龜,好不盛大!
你自然被派遣過去負責採訪這場盛宴。並且他們看在你的才能,決定要讓你Live連線報導,
你知道如果把這個難得的機會搞砸了你可能會變成小明第二。
因此,在開始報導之前你決定先去向前輩烏龜瞭解你的報導方式。
「
你待會要進行的報導方式呢,你看那邊有一條大排長龍的隊伍,共有n隻烏龜排成一列,
你需要選擇一個區間[A,B](包含A, B)進行採訪,採訪的方式是依序遞麥克風給這個區間每一隻烏龜,讓他們自由發言。
必須注意的是因為要弄得看起來很有公信力,你採訪的總人數不能小於L個人。
當然自由發言是有危險成份在的,有些反國王份子可能會講出危言聳聽的話,危害國王聲譽,
所以我們會依序把烏龜標號0或1,0表示危險份子、1則是很安全。
所以,我們希望你能讓這個區間內1佔的比例越大越好,如果有很多個一樣好的區間,
那就是總人數越少越好(但還是得>=L),如果還是有很多個,那就A越小越好。
你選好你要採訪的區間了嗎?告訴我吧。
」
輸入第一行含一個正整數T,表示接下來有幾條隊伍要採訪(幾組詢問)
每組詢問第一行含兩個正整數n, L(L <= n),分別表示隊伍長度跟採訪總人數下限。
第二行會是一個長度為n的01序列,依序表現出每隻烏龜危不危險。
對每組詢問輸出兩個正整數數字A和B,表示[A,B]是你的最佳選擇。
※這個序列編號由1開始,到n為止。
對於第一組範例,[7,11]為11011,1的比例為80%,且他較[10,14]小。
對於第二組範例,[6,9]為1111,1的比例為100%,且他較[12,16]短。
對於100%測資,T <= 400; 1 <= L <= n。
對於10%測資,所有烏龜都不危險
對於30%測資,1 <= n <= 2,000
對於60%測資,1 <= n <= 5,000
對於80%測資,1 <= n <= 20,000
對於100%測資,1 <= n <= 100,000
原TIOJ1670 / 建國中學99年校內培訓contest #1 prob 5
problem setter:ATP
source:ACM-ICPC Regionals
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 8 |
2 | 1 | 8 |
3 | 2 | 8 |
4 | 3 | 8 |
5 | 4 | 8 |
6 | 5 | 8 |
7 | 6 | 8 |
8 | 7 | 8 |
9 | 8 | 8 |
10 | 9 | 8 |
11 | 10 | 8 |
12 | 11 | 12 |