Fişierul intrare/ieşire:	bitsort.in, bitsort.out	Sursă	ad-hoc
Autor	Tudor Muresan	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.05 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Reordonarea șirurilor de biți

Se cere să se reordoneze un şir de biţi specificat. Singura operaţie permisă este interschimbarea unei perechi de biţi adiacenţi. Scrieţi un program care să calculeze numărul minim de interschimbări necesare.

Şirul iniţial de biţi este reprezentat de o secvenţă de biţi, pe când şirul ţintă (final) este dat prin codul lungimilor. Codul lungimilor unui şir de biţi este secvenţa de lungimi ale numărului maximal de 0 sau 1 în şirul de biţi. De exemplu codul lungimilor şirului '011100' este '1 3 2'. De remarcat că există două şiruri de biţi diferite cu acelaşi cod al lungimilor, unul începând cu 0, iar celălalt cu 1, şirul ţintă fiind oricare dintre ele.

În primul exemplu şirul de biţi '100101' trebuie reordonat astfel încât să aibă codul lungimilor '1 3 2', ceea ce înseamnă fie '011100', fie '100011'. Pentru '011100' sunt necesare 4 interschimbări, iar pentru '100011' doar o singură interschimbare, deci răspunsul este 1.

Date de intrare

Fişierul de intrare bitsort.in conţine mai multe linii de test. Fiecare exemplu de test este format din trei linii. Prima linie conţine doi întregi N şi M separaţi printr-un spaţiu. Pe linia următoare este dat şirul de biţi b₁, b₂, ..., b_N, ca valori de 0 şi 1 separate prin spaţiu. Pe a treia linie a fiecărui test este dat codul lungimilor p₁, p₂, ..., p_M.

Fişierul se termină cu o linie care conţine doar valoarea 0.

Date de ieşire

În fişierul de ieşire bitsort.out se va afişa pentru fiecare exemplu de test câte o linie care conţine un singur întreg reprezentând numărul minim de interschimbări cerut.

Restricţii

• 0 ≤ M ≤ N ≤ 15
• 0 ≤ b_i ≤ 1
• p₁ + p₂ + ... + p_M = N
• numărul de teste din fişierul de intrare este cel mult 50

Exemplu

Cum se trimit solutii?