| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 20 | 16 | 13 | 86.667% |
Alice와 Bert는 다양한 보드 게임을 순서대로 플레이하는 다전제 (이를테면 5판 3선승 혹은 7판 4선승) 게임을 즐겨하는데, 너무 자주해서 이제는 조금 특이한 "랜덤 다전제" 놀이를 하기로 했다. 우선, 두 사람은 $N$ 개의 보드 게임을 준비하는데 (편의상 1ドル$ 부터 $N$ 까지 번호가 붙어있다), 각자 상대방보다 잘하는 보드게임이 있어서, $i$ 번째 보드 게임의 승자는 항상 $W_i$ 로 정해져 있다고 가정하자 ($W_i$는 문자열 $W$의 $i$번째 문자이며, $W_i = $A 이면 Alice의 승리, $W_i = $B 이면 Bert의 승리가 예상된다고 한다).
이를테면 $N = 13,ドル $W = $ABABAABBABAAB 라 하면 $W_1 = $A 이므로 1번 보드 게임을 하면 Alice가 이길 것이 예상된다.
다음으로 두 사람은 $M$개의 랜덤 다전제를 정하는데 $j$ 번째 다전제는 두 개의 정수 $(s_j, g_j)$ 로 표현한다 (이 때 $g_j$는 언제나 홀수이다):
예를 들어 $M = 5$ 이고 $s = [1, 3, 11, 12, 13]$ 그리고 $g = [5, 7, 5, 5, 5]$ 라 하자.
A 이므로 5번째 게임을 마친 후 Alice가 최종 승자가 된다. 이 때 $A_1 = 5$ 이다.입력으로 $N, M, W$ 그리고 $s, g$ 배열이 주어졌을 때 $\sum_{j=1}^{M} A_j$ 의 값을 구해보자. 위 예제의 경우 $A = [5, 7, 4, 5, 5]$ 임을 알 수 있으며 따라서 이 경우 정답은 26이다.
입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.
각 테스트 케이스의 첫 줄에는 $N, M$ 이 공백으로 구분되어 주어진다. 둘째 줄에는 A 와 B로만 구성된 길이 $N$인 문자열 $W$가 공백없이 주어진다. 다음 $M$ 줄에 걸쳐서 순서대로 $j$ 번째 랜덤 다전제를 표현하는 두 정수 $(s_j, g_j)$ 가 공백으로 구분되어 주어진다 (1ドル \le j \le M$).
각 테스트 케이스의 정답인 $\sum_{j=1}^{M} A_j$ 를 각 줄에 출력한다.
A 혹은 $W_i = $B3 13 5 ABABAABBABAAB 1 5 3 7 11 5 12 5 13 5 3 3 ABA 1 3 2 3 3 3 5 5 ABABB 1 5 2 5 3 5 4 5 5 5
26 8 23
예제 1: 본문에서 다루었다.
예제 2: 모든 다전제를 Alice가 이기며, $A = [3, 3, 2]$ 이다.
예제 3: 모든 다전제를 Bert가 이기며, $A = [5, 4, 5, 4, 5]$ 이다.