RoAlgo Contest #7 | muxusetre

This was the problem page during the contest. Access the current page here.
Time limit: 0.1s
Memory limit: 1MB
Input:
Output:

"Viața e grea. Mai bine nu treci prin toate greutățile, dă-i skip!"

Mux a fost în parc și a găsit pe o bancă tt șiruri de 00 și 11. El are nevoie să afle câte secvențe bune conține șirul.
Denumim o secvență ca fiind bună, dacă diferența dintre numărul de 00 și numărul de 11 din secvență este pară. Observați că această diferență nu trebuie să fie neapărat pozitivă.

Cerință

Dându-se tt șiruri, spuneți pentru fiecare șir câte secvențe au diferența dintre numărul de 00 și numărul de 11 din secvență număr par.

Date de intrare

Pe prima linie este numărul tt, iar apoi pe a 2i2 \cdot i și pe a 2i+12 \cdot i + 1-a linie (1it)(1 \leq i \leq t) se va afla lungimea celui de-al ii-lea șir găsit de Mux, respectiv șirul.

Date de ieșire

Pe a ii-a linie (1it)(1 \leq i \leq t) se va afla răspunsul la întrebarea lui Mux pentru cel de-al ii-lea șir.

Restricții și precizări

  • 1t1 0001 \leq t \leq 1 \ 000;
  • 1n1061 \leq n \leq 10^6, unde nn este lungimea fiecărui șir
  • Șirul conține doar caracterele 00 și 11.
  • Suma lungimilor celor tt șiruri de caractere nu depășește 10610^6.
  • Notă. Această problemă nu are nicio legătură cu problema suxumetre
# Punctaj Restricții
1 0 Exemplu
2 23 1n1001 \leq n \leq 100
3 36 1n1 0001 \leq n \leq 1 \ 000
4 13 Șirul conține doar 00
5 23 Fără restricții suplimentare

Exemplu

stdin

4
9
010100100
7
0000000
18
100100010111010111
11
00000000000

stdout

20
12
81
30

Explicație

Pentru primul șir, câteva din subsecvențele ce respectă proprietatea cerută sunt 0101, 10, 1001 etc.

Contest info

Official contest

Start time: 1699171200000

Total duration: 4h0m0s

Status: Ended

Log in or sign up to be able to send submissions!