== include(page="template/taskheader" task_id="mirror") ==
Poveste şi cerinţă...
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.
h2. 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.
h2. Date de intrare
Fişierul de intrare $mirror.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $mirror.out$ ...
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).
h2. 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.$
h2. Exemplu
table(example). |_. mirror.in |_. mirror.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
table(example). |_. 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
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="mirror") ==
