ŠIOM — Griežta disjunkcija

Laiko ribojimas: 1s

Atminties ribojimas: 128MB

Duomenų failas: griezta_disjunkcija.in

Rezultatų failas: griezta_disjunkcija.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Griežta disjunkcija

Prieš pradėdami kalbėti apie pačią užduotį, apibrėžkime griežtos disjunkcijos operaciją. Griežta disjunkcija yra dvinarė operacija, kurią galima užrašyti taip a\b, kur a ir b yra kintamieji, įgyjantys kokias nors dvi reikšmes. Kad būtų paprasčiau, įsivaizduokime, kad a yra kintamasis, atsakantis į klausimą ar Jonas yra kine, o b ar Jonas yra namie. Dabar galime apibrėžti operaciją tokia lentele:

a	b	rezultatas
kine kine ne kine ne kine	namie ne namie namie ne namie	ne taip taip ne

arba žymint teigiamą atsakymą 1, o neigiamą 0:

a	b	rezultatas
1 1 0 0	1 0 1 0	0 1 1 0

Kitaip tariant, griežta disjunkcija atsako į klausimą ar Jonas yra išvykęs į kiną, o gal jis sėdi namie (Jonas būti abejose vietose negali)?

Dabar galime pasižiūrėti į pačia užduotį :)

Sakykime, turime seką, sudarytą iš $N$ natūraliųjų skaičių, užrašytų dvejetainiu pavidalu. Kiekvienai gretimai skaičių $a_i$ ir $a_{i+1}$ porai galime atlikti griežtos disjunkcijos operaciją pabičiui ir taip gauti naują skaičių $b$ (šį skaičių vadinsime griežtos disjunkcijos keitiniu). Šis skaičius pirminėje sekoje pakeičia skaičius $a_i$ ir $a_{i+1}$ (t.y. gauname seką, sudarytą iš $N-1$ elementų). Tokią keitimo operaciją galime kartoti kiek tik norime.

Galiausiai iš likusių skaičių parenkame didžiausią (pagal dešimtainį ekvivalentą) ir šį skaičių paskelbiame griežtos disjunkcijos keitinių rezultatu. Jums reikia rasti didžiausią griežtos disjunkcijos keitinių rezultatą.

Pavyzdžiui, jei pirminė seka yra.

optimalūs keitimai (kurių gale gauname didžiausią griežtos disjunkcijos keitinių rezultatą) yra:

```
1001
0101
0010
0111
```
```
1001
0111
0111
```
```
1110
0111
```

Ir taip galutinis atsakymas yra: 1110

Pradiniai duomenys

Skaičius $N$ ( $1\\leqN\\leq100000$ ), nurodantis pirminės sekos ilgį. Toliau seka $N$ eilučių, kurių kiekvienoje nurodytas skaičius $a_i$ ( $0\\leqa_i\\leq10^{18}$ ) dvejetainiu pavidalu.

Rezultatai

Dvejetainis skaičius (trumpiausiu pavidalu), nurodantis didžiausią griežtos disjunkcijos keitinių rezultatą.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
5 1001 0101 0010 0011 0100	1110

Šeštadieninė informatikos olimpiadininkų mokykla

Griežta disjunkcija

Pradiniai duomenys

Rezultatai

Pavyzdžiai