Laiko ribojimas: 0.5s

Atminties ribojimas: 10MB

Duomenų failas: griezta_disjunkcija2.in

Rezultatų failas: griezta_disjunkcija2.out

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.

1001
0101
0010
0011
0100

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

  1. 1101
    0101
    0010
    0011
  2. 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