| Fișierul intrare/ieșire | mirror.in, mirror.out | Sursă | ONI 2017, clasa a 9-a |
|---|---|---|---|
| Autor | Mirela Mlisan | Adăugată de |
Cojocaru Alexandru
•
alex.cojocaru
|
| Timp de execuție pe test | 0.4 sec | Limită de memorie | 32768 KB |
| Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Mirror
Numim „oglinda” numărului natural nenul a, numărul b, obținut prin modificarea fiecărei cifre din reprezentarea sa binară, de exemplu pentru a=22(10) =10110(2) se obține 01001(2) = 9(10) = b.
Cerințe:
Cunoscându-se numerele naturale N, K și cele N numere natural nenule, scrieți un program care:
1) Transformă în baza doi termenii șirului dat obținându-se un nou șir format din alipirea cifrelor binare. Din acest șir se vor determina și afișa, separate prin câte un spațiu, toate reprezentările în baza 10 corespunzătoare secvențelor alăturate de exact K cifre binare, parcurse de la stânga la drepta. Dacă ultima secvență nu are exact K cifre binare, atunci aceasta nu se va mai lua în considerare.
2) Să aplice K transformări asupra șirului inițial, înlocuind la fiecare pas orice termen cu „oglinda” sa. Asupra termenilor care devin zero nu se vor mai efectua alte operații. După efectuarea celor K transformări, să se determine cea mai lungă secvență de numere care au cifra 1 pe aceeași poziție în reprezentarea lor în baza doi. Dacă sunt mai multe astfel de secvențe având lungimea maximă, se va afișa cea mai din stânga.
Date de intrare
Fișierul de intrare mirror.in conține pe primul rând numărul C, reprezentând cerința. Pe al doilea rând se află scrise numerele naturale N și K. Pe rândul al treilea sunt cele N numere ale șirului separate prin câte un spațiu.
Date de ieșire
Dacă C=1, atunci în fișierul de ieșire mirror.out se vor scrie separate prin câte un spațiu, toate numerele cerute în enunț.
Dacă C=2, atunci în fișierul de ieșire mirror.out se va scrie pe prima linie lungimea maximă a secvenței determinate, iar pe următoarea linie separate prin spațiu, poziția primului și ultimului termen din secvență (prima poziție este 1).
În fișierul de ieșire mirror.out ...
Restricții
- 1 ≤ N ≤ 100000
- 0 ≤ K ≤ 30
- Elementele șirului sunt mai mici decât 2000000001
- Pentru 30% din teste cerința va fi C=1.
Exemplu
| mirror.in | mirror.out | Explicație |
|---|---|---|
| 1 4 2 7 8 2 11 |
3 3 0 1 1 1 |
7(10)=111(2); 8(10)=1000(2); 2(10)=10(2); 11(10)=1011(2); Sirul format este: {11}11{00}01{01}01{1} și grupate câte 2 avem numerele: 11(2)=3(10); 11(2)=3(10); 00(2)=0(10); 01(2)=1(10); 01(2)=1(10); 01(2)=1(10); |
| 2 5 1 37 72 101 50 116 |
3 1 3 |
După o transformare numerele în baza 2 sunt: 0 0 {1} 1 0 {1} 0 <-37 0 1 {1} 0 1 {1} 1 <-72 0 0 {1} {1} 0 {1} 0 <-101 0 0 0 {1} 1 0 1 <-50 0 0 0 {1} 0 0 0 <-116 Cea mai lungă secvență este de lungime 3, fiind formată din numerele 37, 72, 101 care începe pe poziția 1 și se termină pe poziția 3. Mai există încă o astfel de secvența (101, 50, 116) dar se alege cea mai |
