ŠIOM — Griežta disjunkcija 2

Laiko ribojimas: 0.5s

Atminties ribojimas: 10MB

Duomenų failas: griezta_disjunkcija2.in

Rezultatų failas: griezta_disjunkcija2.out

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

Griežta disjunkcija 2

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 skaičių $a_i$ ir $a_j$ 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_j$ (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:

```
1101
0101
0010
0011
```
```
1111
0101
0011
```

Ir taip galutinis atsakymas yra: 1111

Pradiniai duomenys

Skaičius $N$ ( $1\\leqN\\leq500000$ ), 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	1111

Šeštadieninė informatikos olimpiadininkų mokykla

Griežta disjunkcija 2

Pradiniai duomenys

Rezultatai

Pavyzdžiai