570 . 均值定理

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Andy8787

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (4/4)

Tags

apcsc apcsc-string

Description

身為均值理論（Mean Value Theorem）的支持者，賽先生生活的一切都跟均衡脫不了關係：吃肯O雞永遠不會只點蛋塔、打麻將永遠都是平均放槍給另外三家、APCSC 更是每年都參加，絕不偏袒任何一年。

最近賽先生看到了朋友桃子寄給他、且只由字母 x 跟 y 組成的字串 $s$，基於均值理論，賽先生相信這個字串一定也跟均衡有所關係：他認為字串中的某個區間裡，字母 x 跟字母 y 的出現次數會相等，此時這個區間稱作「均衡」，但因為賽先生的數學真的太爛了，所以決定請你來幫忙他找出一段均衡的區間。

Input Format

輸入的第一行有一個正整數 $t\ (1\le t\le 1000)$ 代表測試資料的數量。

每一筆測試資料有兩行，第一行包含一個正整數 $n\ (1\le n\le 50)$，代表桃子寄來的字串長度。

第二行包含一個長度為 $n$ 的字串，代表桃子寄來的字串，字串內容僅由 x 跟 y 兩種字母組成。

Output Format

對於每一筆測資請輸出一行，如果該字串中存在均衡區間，請輸出區間左、右界的索引值（區間包含左右界，從 $1$ 開始算），兩者之間以空格分隔，如果有多個區間，輸出任意一組區間即可；如果不存在均衡區間，請輸出 -1 -1。

Sample Input 1

4
1
x
6
xyyxyx
6
xyyxyx
9
yxyyxyyxx

Sample Output 1

-1 -1
3 6
1 6
4 9

Hints

Problem Source

Codeforces 1569A

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~10 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
Submit
Back to Top