== include(page="template/taskheader" task_id="dispozitiv") ==
<tex> a_1 </tex>
!>problema/dispozitiv?poza_noua_dispozitiv2.png!
În Ţinutul Ooo, Regele Gheaţă a aruncat un blestem asupra Prinţesei Gumiţă. Ea a primit un şir binar <tex> a_1 </tex>, alcătuit din 0-uri şi 1-uri.
În Tărâmul Ooo, Regele Gheaţă a aruncat un blestem asupra Prinţesei Gumiţă. Ea a primit un string binar $a{~1~} a{~2~} ... a{~N~}$, alcătuit din 0-uri şi 1-uri.
Pentru a rupe blestemul, Finn şi Jake au primit de la BMO un dispozitiv magic. Dispozitivul poate fi folosit pe orice subsecvenţă de lungime exact $k$, inversând fiecare bit din acesta (adică 0 devine 1 şi 1 devine 0).
Pentru a rupe blestemul, Finn şi Jake au primit de la BMO un dispozitiv magic. Dispozitivul poate fi folosit pe orice subsecvenţă de lungime exact $K$, inversând fiecare bit din aceasta (adică 0 devine 1 şi 1 devine 0).
Scopul lor este să transforme întreg şirul în 0-uri, dacă este posibil.
Însă Regele Gheaţă nu stă degeaba. El intervine de $q$ ori, iar de fiecare dată schimbă (inversează) un singur bit din şir, la o poziţie aleasă de el. După fiecare astfel de modificare, Finn şi Jake trebuie să verifice din nou dacă şirul poate fi adus la forma cu toate 0-uri, folosind dispozitivul magic.
Însă Regele Gheaţă nu stă degeaba. El intervine de $Q$ ori, iar de fiecare dată schimbă (inversează) un singur bit din şir, la o poziţie aleasă de el. După fiecare astfel de modificare, Finn şi Jake trebuie să verifice din nou dacă şirul poate fi adus la forma cu toate 0-uri, folosind dispozitivul magic. În plus, ei trebuie sa verifice si pentru şirul initial.
h2. Date de intrare
Fişierul de intrare $dispozitiv.in$ ...
Fişierul de intrare $dispozitiv.in$ este organizat astfel:
Pe prima linie se află $T$, numărul de teste.
Pentru fiecare test:
* Pe prima linie se află $N$, $K$.
* Pe a doua linie se afla string-ul binar $a$ de lungime $N$.
* Pe a treia linie se află numărul $Q$.
* Pe următoarele $Q$ linii se află câte un număr $p$, cu semnificaţia că Regele Gheaţă a inversat bit-ul $p$.
h2. Date de ieşire
În fişierul de ieşire $dispozitiv.out$ ...
În fişierul de ieşire $dispozitiv.out$ se va afişa astfel:
* Pentru fiecare test, se vor afişa $Q+1$ linii. Pe fiecare linie se va afla $YES$, daca toate valorile pot fi făcute $0$ sau $NO$ altfel.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10 000$
* $1 ≤ K ≤ N ≤ 200 000$
* $1 ≤ Q ≤ 200 000$
* Fie $S_N$ suma tuturor $N$-urilor dintr-un test de evaluare. Se garantează că $S_N ≤ 200 000$.
* Fie $S_Q$ suma tuturor $Q$-urilor dintr-un test de evaluare. Se garantează că $S_Q ≤ 200 000$.
|_. # |_. Punctaj |_. Restricţii |
| 1 | 6 | $S_N, S_Q <= 200$ |
| 2 | 15 | $S_N, S_Q <= 2 000$ |
| 3 | 7 | $K = N$ |
| 4 | 15 | $K = 2$ |
| 5 | 24 | $K ≤ 10$ |
| 6 | 33 | Fără alte restricţii |
h2. Exemplu
table(example). |_. dispozitiv.in |_. dispozitiv.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|_. dispozitiv.in |_. dispozitiv.out |
| 3
5 2
01100
3
1
2
3
7 3
1010110
5
2
7
4
1
5
10 5
0011001001
2
2
3 | YES
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
|
h3. Explicaţie
...
În primul test, şirul este iniţial $01100$ şi putem inversa substring-uri de lungime exact $K = 2$. $01100$ poate fi transformat în $00000$ prin inversarea substring-ului $[2, 3]$.
După prima actualizare, şirul devine $11100$. Se pare că acesta nu poate fi transformat în $00000$.
După a doua actualizare, şirul devine $10100$, care poate fi transformat în şir de zerouri prin inversarea substring-ului $[1, 2]$ (şirul devine $01100$), apoi prin inversarea substring-ului $[2, 3]$.
== include(page="template/taskfooter" task_id="dispozitiv") ==
