Revizia anterioară Revizia următoare
| 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 maxim 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 ...
Date de ieşire
În fişierul de ieşire bitsort.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| bitsort.in | bitsort.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
