시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 256 MB51343063.830%

문제

It’s dinner time, and Busy Beaver has to feed his baby beavers.

Busy Beaver has $N$ baby beavers, numbered from $1$ to $N$. The older baby beavers have bigger indices than the younger ones; for example, beaver $1$ is the youngest while beaver $N$ is the oldest.

Busy Beaver also has $2N$ dishes, which are numbered from $1$ to $2N$. If a beaver eats dish $i$, its satisfaction will increase by $i$. Each beaver starts with $0$ satisfaction.

Now, Busy Beaver wants to distribute the dishes amongst his baby beavers subject to the following constraints:

  • Each beaver should get exactly two dishes.
  • After all dishes are consumed, older beavers should have at least as much satisfaction as younger beavers. Formally, for any $i,j$ with $1\leq i<j\leq N$, beaver $i$’s satisfaction should not exceed beaver $j$’s satisfaction.
  • The parity of beaver $i$’s satisfaction should be $c_i$ (odd or even).

Determine if there exists a way to feed all $N$ beavers that respects these constraints. Additionally, if the task is possible, print any valid assignment of dishes to beavers.

입력

Each test contains multiple test cases. The first line contains a single integer $T$ ($1\leq T\leq 10^4$) --- the number of test cases. The description of each test case follows.

The first line of each test case contains an integer $N$ ($1\le N\le 10^5$) --- the number of baby beavers.

The second line of each test case contains a string $c$ of length $N$, where each of the characters $c_i$ is either ‘O’ or ‘E’. If $c_i$ is ‘O’, the beaver $i$ wants its satisfaction to be an odd number. If $c_i$ is ‘E’, the beaver $i$ wants its satisfaction to be an even number.

It is guaranteed that the sum of $N$ across all test cases is no more than $10^5$.

출력

For each test case, if it is possible to feed the beavers, output “YES” (without quotes) on the first line. Next, print $N$ lines describing how to feed each beaver. The $i$-th of these lines should contain two integers, which denote the indices of the two dishes that will be given to beaver $i$.

If it is impossible to feed the beavers, output “NO” (without quotes).

You can output “YES” and “NO” in any case. (For example, strings “yES”, “yes” and “Yes” will be recognized as a positive response.)

서브태스크

번호배점제한
125

For each test case, the string $c$ either only consists of ‘O’s or only consists of ‘E’s.

275

No additional constraints.

예제 입력 1

3
4
OEEO
7
OEOEOEO
6
OOOOOO

예제 출력 1

YES
2 3
5 1
4 8
7 6
NO
YES
1 12
2 11
3 10
4 9
5 8
6 7

In the first test case, one possible way to feed the beavers is as follows:

  • Feed dishes $2$ and $3$ to beaver $1$. Beaver $1$ gains satisfaction of $5$, which is odd.
  • Feed dishes $5$ and $1$ to beaver $2$. Beaver $2$ gains satisfaction of $6$, which is even.
  • Feed dishes $4$ and $8$ to beaver $3$. Beaver $3$ gains satisfaction of $12$, which is even.
  • Feed dishes $7$ and $6$ to beaver $4$. Beaver $4$ gains satisfaction of $13$, which is odd.

The satisfaction of the four beavers in increasing order of age are $[5,6,12,13]$. It can be checked that this assignment satisfies the conditions.

In the second test case, it can be shown that the task is impossible.

출처

University > MIT > M(IT)^2 > M(IT)^2 Spring 2025 Invitational > Qualification Round 1 3번

  • 문제를 만든 사람: 79brue

채점 및 기타 정보

  • 예제는 채점하지 않는다.