Pracsiu Dan (dnprx) Un număr natural se numește extrapar dacă poate fi scris ca sumă de puteri distincte ale lui 2, puteri care au exponent par. Numărul 0 este considerat, de asemenea, extrapar. Considerând reprezentarea în baza 2 pentru un număr natural, se numerotează pozițiile cifrelor din reprezentare, de la dreapta către stânga, începând cu 0. Asupra reprezentării în baza 2 trebuie să se efectueze o singură operație. Operația constă din eliminarea a exact K cifre situate pe poziții consecutive.
Cerința
Fiind date reprezentările în baza 2 pentru N numere naturale, să se determine pentru fiecare dintre ele dacă se poate obține un număr extrapar în condițiile de mai sus.
Date de intrare
Fișierul de intrare extrapare.in conține pe prima linie două numere naturale N K, separate printr-un spațiu. Pe fiecare dintre următoarele N linii se află reprezentarea în baza 2 a unui număr natural.
Date de ieșire
Fișierul de ieșire extrapare.out va conține N linii. Pe cea de a i-a linie (1 ≤ i ≤ N) se va afișa reprezentarea în baza 2 a numărului extrapar obținut prin efectuarea unei singure operații asupra celei de a i-a reprezentări din fișierul de intrare, sau valoarea -1 dacă obținerea unui număr extrapar nu este posibilă în acest mod.
Restricții și precizări
0 < N ≤ 100 ≤ K < numărul de cifre din oricare reprezentare din fișierul de intrare- Orice reprezentare din fișierul de intrare are cel mult
1.000.000de cifre. - Dacă există mai multe modalități de a efectua o operație astfel încât rezultatul să fie un număr extrapar, se va afișa rezultatul pentru acea operație în care poziția primei cifre eliminate este cea mai mare (cea mai din stânga poziție).
- Se garantează că reprezentările în baza 2 din fișierul de intrare au cifra cea mai din stânga egală cu 1.
- Reprezentarea în baza 2 a numărului rezultat în urma efectuării operației se va afișa fără zerourile nesemnificative ce se pot forma la stânga lui.
- Pentru 19 puncte,
K = 0 - Pentru 32 puncte,
K > 0și lungimea șirurilor≤ 1000. - Pentru 49 puncte,
K > 0și lungimea șirurilor≤ 1.000.000.
Exemplu:
extrapare.in
9 3 1001101 1010000010 101010001 111010100 100100 100010100 101000001 11110 101000
extrapare.out
-1 1010000 10001 10100 100 10100 1 -1 0
Explicație
Trebuie să eliminăm 3 cifre pentru a forma numere extrapare.
- Numerele pentru care nu se poate obține un număr extrapar prin eliminarea a trei cifre de pe poziții consecutive sunt primul și al optulea.
- Din 1010000010 tăiem cifrele de pe pozițiile 0, 1 și 2 și obținem 1010000.
- 101010001 este deja extrapar și vom elimina cele mai din stânga trei cifre.
- Observăm că dacă rezultatul este format doar din cifre egale cu 0 se va afișa un singur 0.
Și așa mai departe.