Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

De som har løst Conference*, vil naturlig nok kunne komme på dette problemet.

Du får gitt en streng $S$ med lengde $N$. Hvert tegn i $S$ er ett av A, B, C eller ?. Spesielt er det første og det siste tegnet i $S$ lik A.

For en streng med lengde $N$ som kun består av A, B og C, definerer vi poengsummen dens som antallet heltall $i$ ($1 \le i \le N - 1$) slik at det $i$-te tegnet og det $(i + 1)$-te tegnet er forskjellige.

Du får gitt $Q$ spørringer. Den $i$-te spørringen er som følger:

Ikke-negative heltall $X_i, Y_i, Z_i$ er gitt, der $X_i + Y_i + Z_i$ er lik antallet ?-tegn i $S$. Blant alle strenger som oppnås ved å erstatte $X_i$ av ?-tegnene i $S$ med A, $Y_i$ av dem med B og $Z_i$ av dem med C, skriv ut den maksimalt mulige poengsummen.

Inndata

Inndataene gis på følgende format:

N
S
Q
X_1 Y_1 Z_1
X_2 Y_2 Z_2
:
X_Q Y_Q Z_Q

Utdata

Skriv ut $Q$ linjer. På den $i$-te linjen skal du skrive ut svaret på den $i$-te spørringen.

Begrensninger

  • $N, Q, X_i, Y_i, Z_i$ er heltall.
  • $2 \le N \le 3 \times 10^5$
  • $S$ er en streng med lengde $N$ som består av A, B, C og ?.
  • Det første og det siste tegnet i $S$ er A.
  • $1 \le Q \le 2 \times 10^5$
  • $0 \le X_i$
  • $0 \le Y_i$
  • $0 \le Z_i$
  • $X_i + Y_i + Z_i$ er lik antallet ?-tegn i $S$.

Eksempler

Inndata 1

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

Utdata 1

8
6
4

Inndata 2

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

Utdata 2

4
8
4
10

Inndata 3

28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13

Utdata 3

24
21
23
21
19
20
19
21
19
17
19
22
19
17
22
19
23
22
20
13
15
19
20
17
21
17

Merk

I det første eksempelet:

  • For den første spørringen gir det å erstatte tegnene som ABCBABCBA en poengsum på $8$, som er det maksimalt mulige.
  • For den andre spørringen gir det å erstatte tegnene som ABABAACAA en poengsum på $6$.
  • For den tredje spørringen gir det å erstatte tegnene som ACCBCCCCA en poengsum på $4$.

* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1417EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.