Þeir sem hafa leyst Conference* gætu eðlilega dottið þetta verkefni í hug.
Gefinn er strengur $S$ af lengd $N$. Hvert tákn í $S$ er eitt af A, B, C eða ?. Sérstaklega eru fyrsta og síðasta táknið í $S$ bæði A.
Fyrir streng af lengd $N$ sem samanstendur eingöngu af A, B og C skilgreinum við stig hans sem fjölda heiltalna $i$ ($1 \le i \le N - 1$) þannig að $i$-ta táknið og $(i + 1)$-ta táknið séu ólík.
Gefnar eru $Q$ fyrirspurnir. $i$-ta fyrirspurnin er sem hér segir:
Gefnar eruóneikvæðar heiltölur $X_i, Y_i, Z_i$, þar sem $X_i + Y_i + Z_i$ er jafnt fjölda ?-tákna í $S$. Meðal allra strengja sem fást með því að skipta út $X_i$ af ?-táknunum í $S$ fyrir A, $Y_i$ þeirra fyrir B og $Z_i$ þeirra fyrir C, prentið hæstu mögulegu stigin.
Inntak
Inntakið er gefið á eftirfarandi sniði:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Úttak
Prentið $Q$ línur. Á $i$-tu línu skal prenta svarið við $i$-tu fyrirspurninni.
Skorður
- $N, Q, X_i, Y_i, Z_i$ eru heiltölur.
- $2 \le N \le 3 \times 10^5$
- $S$ er strengur af lengd $N$ sem samanstendur af
A,B,Cog?. - Fyrsta og síðasta táknið í $S$ eru
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 jafnt fjölda
?-tákna í $S$.
Dæmi
Inntak 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Úttak 1
8 6 4
Inntak 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Úttak 2
4 8 4 10
Inntak 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
Úttak 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
Athugasemd
Í fyrsta dæminu:
- Fyrir fyrstu fyrirspurnina gefur útskipting táknanna í
ABCBABCBAstigin $8$, sem er mesta mögulega gildið. - Fyrir aðra fyrirspurnina gefur útskipting táknanna í
ABABAACAAstigin $6$. - Fyrir þriðju fyrirspurnina gefur útskipting táknanna í
ACCBCCCCAstigin $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf