TopCoder

User's AC Ratio

69.6% (16/23)

Submission's AC Ratio

19.0% (42/221)

Tags

Description

「我與小明不相見已有二年餘了,我最不能忘記的是他的雙腿。(雖然他根本沒有)」

光陰荏苒,你如今是一位御用新聞記者,專門替國王烏龜的電視台採訪各式各樣的新聞。
還記得TIOJ 1623--國王烏龜的接駁車嗎?大意就是國王烏龜開放死老百姓烏龜們去覲見國王,
舉國上下無不歡聲雷動,一時之間各個直達皇宮接駁車的站牌前都排滿了烏龜,好不盛大!

你自然被派遣過去負責採訪這場盛宴。並且他們看在你的才能,決定要讓你Live連線報導,
你知道如果把這個難得的機會搞砸了你可能會變成小明第二。

因此,在開始報導之前你決定先去向前輩烏龜瞭解你的報導方式。

你待會要進行的報導方式呢,你看那邊有一條大排長龍的隊伍,共有n隻烏龜排成一列,
你需要選擇一個區間[A,B](包含A, B)進行採訪,採訪的方式是依序遞麥克風給這個區間每一隻烏龜,讓他們自由發言。
必須注意的是因為要弄得看起來很有公信力,你採訪的總人數不能小於L個人。

當然自由發言是有危險成份在的,有些反國王份子可能會講出危言聳聽的話,危害國王聲譽,
所以我們會依序把烏龜標號0或1,0表示危險份子、1則是很安全。

所以,我們希望你能讓這個區間內1佔的比例越大越好,如果有很多個一樣好的區間,
那就是總人數越少越好(但還是得>=L),如果還是有很多個,那就A越小越好。

你選好你要採訪的區間了嗎?告訴我吧。

Input Format

輸入第一行含一個正整數T,表示接下來有幾條隊伍要採訪(幾組詢問)
每組詢問第一行含兩個正整數n, L(L <= n),分別表示隊伍長度跟採訪總人數下限。
第二行會是一個長度為n的01序列,依序表現出每隻烏龜危不危險。

Output Format

對每組詢問輸出兩個正整數數字A和B,表示[A,B]是你的最佳選擇。
※這個序列編號由1開始,到n為止。

Sample Input 1

2
17 5
00101011011011010
20 4
11100111100111110000

Sample Output 1

7 11
6 9

Hints

對於第一組範例,[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

Problem Source

原TIOJ1670 / 建國中學99年校內培訓contest #1 prob 5
problem setter:ATP
source:ACM-ICPC Regionals

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10
10 3000 65536 262144 11
11 3000 65536 262144 12