Problem 473: Quantum Computing

Quantum Computing este o tehnologie nouă ce folosește proprietățile mecanicii cuantice pentru a efectua anumite calcule într-un timp mult mai scurt decât este capabil să le facă un calculator clasic. Diferența fundamentală dintre un calculator clasic și unul cuantic este modul în care procesează informația. Un calculator clasic procesează informația folosind biți, care pot fi $0$ sau $1$ . Pe de altă parte, un calculator cuantic utilizează qubiți, care pot avea în același timp și valoarea $0$ (notată cu $| 0 \rangle$ ) și valoarea $1$ (notată cu $| 1 \rangle$ ) - spunem că qubitul se află în starea cuantică $| \psi \rangle = \alpha | 0 \rangle + \beta |1 \rangle$ . Efectuând modificări asupra acestor qubiți, putem dezvolta algoritmi cuantici cu o complexitate mai bună decât a celor mai buni algoritmi clasici existenți. Totuși, calculatoarele cuantice nu au încă utilitate practică deoarece nu dispun de un număr suficient de mare de qubiți (la ora actuală cele mai puternice calculatoare cuantice au câteva sute de qubiți). Pentru simplitate, vom lucra doar cu stări pure ( $| 0 \rangle$ sau $| 1 \rangle$ ).

Să considerăm un calculator cuantic cu $N$ qubiți setați inițial la $| q_1 \rangle | q_2 \rangle .. | q_N \rangle$ . Asupra acestor qubiți se poate efectua un singur tip de operații: se inversează toți qubiții ( $| 0 \rangle$ devine $| 1 \rangle$ și vice versa) dintr-o subsecvență (qubiți aflați pe poziții consecutive). Exemplu: $| 0 \rangle | 0 \rangle | 1 \rangle | 0 \rangle$ devine $| 0 \rangle | 1 \rangle | 0 \rangle | 1 \rangle$ dacă se inversează qubiții de pe pozițiile $2$ , $3$ și $4$ . O particularitate nefericită a unui calculator cuantic este că fiecare operație introduce erori (de exemplu, este posibil ca un qubit să nu se inverseze, deși ar trebui să o facă). De aceea, este necesar ca un algoritm cuantic să efectueze un număr cât mai mic de operații.

Cerință

Aflați numărul minim de operații necesare pentru a seta toți qubiții la $| 1 \rangle$ în situațiile:

Operațiile se pot efectua asupra subsecvențelor de orice lungime;
Operațiile se pot efectua doar asupra subsecvențelor de lungime $K$ .

Date de intrare

Datele de intrare conţin pe prima linie două numere întregi $C$ și $T$ , separate printr-un spațiu, unde $C$ reprezintă tipul cerinței și $T$ numărul de teste. Pe următoarele linii se află descrierea testelor.

Dacă $C=1$ atunci pe prima linie a fiecărui test se află numărul întreg $N$ , reprezentând numărul de qubiți, iar pe a doua linie se află $N$ caractere reprezentând starea inițială a qubiților ( $| 0 \rangle$ este reprezentat prin $"0"$ și $| 1 \rangle$ este reprezentat prin $"1"$ ).

Dacă $C=2$ atunci pe prima linie a fiecărui test se află două numere întregi $N$ și $K$ , separate printr-un spațiu, reprezentând numărul de qubiți și lungimea unei subsecvențe pe care se poate efectua o operație, iar pe a doua line starea inițială a qubiților, descrisă la fel ca pentru $C=1$ .

Date de ieșire

Se vor afișa $T$ linii, pe fiecare linie aflându-se numărul minim de operații necesare pentru a seta toți qubiții la $| 1 \rangle$ . Pentru $C=1$ se garantează că există mereu o soluție. Pentru $C=2$ , dacă nu există soluție, se va afișa $-1$ .

Restricții și precizări

$1 \leq T \leq 10$ ;
$1 \leq K \leq N \leq 10^6$ ;
suma valorilor lui $N$ pe toate testele nu va depăși $10^6$ ;
Subtask $1$ ( $40$ p): $C = 1$ ;
Subtask $2$ ( $20$ p): $C = 2$ și $N \leq 1 \ 000$ ;
Subtask $3$ ( $40$ p): $C = 2$ .

Exemplul 1

stdin

stdout

2
3

Explicație

Exemplul 2

stdin

2 2 
12 4 
110100100000 
5 2 
01100

stdout

4
-1

Explicație

Pentru al doilea test, se poate demonstra că nu există soluție.

Quantum Computing

Cerință

Date de intrare

Date de ieșire

Restricții și precizări

Exemplul 1

Explicație

Exemplul 2

Explicație

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