Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Ceux qui ont résolu Conference* peuvent naturellement imaginer ce problème.

On vous donne une chaîne de caractères $S$ de longueur $N$. Chaque caractère de $S$ est l'un de A, B, C ou ?. En particulier, le premier et le dernier caractère de $S$ sont A.

Pour une chaîne de longueur $N$ composée uniquement de A, B et C, on définit son score comme le nombre d'entiers $i$ ($1 \le i \le N - 1$) tels que le $i$-ième caractère et le $(i + 1)$-ième caractère soient différents.

On vous donne $Q$ requêtes. La $i$-ième requête est la suivante :

Des entiers non négatifs $X_i, Y_i, Z_i$ sont donnés, où $X_i + Y_i + Z_i$ est égal au nombre de caractères ? dans $S$. Parmi toutes les chaînes obtenues en remplaçant $X_i$ des caractères ? de $S$ par A, $Y_i$ d'entre eux par B et $Z_i$ d'entre eux par C, affichez le score maximum possible.

Entrée

L'entrée est donnée dans le format suivant :

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

Sortie

Affichez $Q$ lignes. Sur la $i$-ième ligne, affichez la réponse à la $i$-ième requête.

Contraintes

  • $N, Q, X_i, Y_i, Z_i$ sont des entiers.
  • $2 \le N \le 3 \times 10^5$
  • $S$ est une chaîne de longueur $N$ composée de A, B, C et ?.
  • Le premier et le dernier caractère de $S$ sont 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$ est égal au nombre de caractères ? dans $S$.

Exemples

Entrée 1

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

Sortie 1

8
6
4

Entrée 2

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

Sortie 2

4
8
4
10

Entrée 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

Sortie 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

Note

Dans le premier exemple :

  • Pour la première requête, remplacer les caractères sous la forme ABCBABCBA donne un score de $8$, ce qui est le maximum possible.
  • Pour la deuxième requête, remplacer les caractères sous la forme ABABAACAA donne un score de $6$.
  • Pour la troisième requête, remplacer les caractères sous la forme ACCBCCCCA donne un score de $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.