Odavno se zna za mistična svojstva nizova kojima je i bitovska konjunkcija svih elemenata veća od nule i bitovska ekskluzivna disjunkcija veća od nule. Čarobnjak Vizaard je dobio jedan ovakav niz sa \(N\) elemenata. Da bi on dobio mistična svojstva, Vizaard na svakom od njegovih elemenata može da primeni jednu od sledeće dve operacije:
- Ukoliko je \(A_{i} > 0\), može da smanji vrednost elementu sa indeksom \(i\). Ovom operacijom vrednost \(i\)-tog elementa se pretvara u \(A_{i}-1\).
- Može da poveća vrednost elementu sa indeksom
. Ovom operacijom vrednost
-tog elementa se pretvara u
.
Vizaarda interesuje koliko najmanje operacija mora da primeni tako da niz dobije mistična svojstva, tj. da mu bitovska konjunkcija svih elemenata bude veća od nule i da mu bitovska ekskluzivna disjunkcija svih elemenata bude veća od nule.
Opis ulaza
U prvoj liniji nalazi se jedan broj , dužina niza. U narednoj liniji nalazi se niz od
elemenata.
Opis izlaza
Ispisati najmanji broj operacija potrebnih da i bitovska konjunkcija i bitovska ekskluzivna disjunkcija svih elemenata bude veća od .
Primer
Ulaz
4
5 2 3 3
Izlaz
1
Objašnjenje primera
Primetimo da je \(5 \ \text{and} \ 2 \ \text{and} \ 3 \ \text{and} \ 3 = 0\). Međutim primetimo da ukoliko drugi element smanjimo za jedan, dobijamo niz \([5,1, 3, 3]\), za koji važi \(5 \ \text{and} \ 1 \ \text{and} \ 3 \ \text{and} \ 3 = 1\) i \(5 \ \text{xor} \ 1 \ \text{xor} \ 3 \ \text{xor} \ 3 = 4\).
Ograničenja
Postoje četiri podzadatka:
- Podzadatak 1 [14 poena]:
.
- Podzadatak 2 [20 poena]: \(N \leq 10^3\), \(A_{i} \leq 10^9\).
- Podzadatak 3 [29 poena]:
,
.
- Podzadatak 4 [37 poena]: Nema dodatnih ograničenja.
Napomena
Operator konjunkcije u Pascal-u je označen sa and
, dok u C++ ga zapisujemo pomoću simbola &
. Ova operacija se za nenegativne cele brojeve
definiše na sledeći način. Prvo se brojevi zapišu u binarnom zapisu. Ukoliko jedan broj ima manje cifara od drugog, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih cifara. Tako se dobijaju dva niza binarnih cifara, označimo ih sa
i
. Zatim se za svaku poziciju
računa
pomoću sledećih pravila:
- Za
važi
- Za
važi
- Za
važi
- Za
važi
Niz binarnih cifara (koji možda ima vodeće nule) je binarni zapis rezultata, odnosno broja
.
Bitovska konjunkcija između elemenata
definiše se kao
.
Operator ekskluzivne disjunkcije u Pascal-u je označen sa xor
, dok u C++ ga zapisujemo pomoću simbola ^
. Ova operacija \(x\ \text{xor} \ y\) se za nenegativne cele brojeve \(x,y\) definiše na sledeći način. Prvo se brojevi zapišu u binarnom zapisu. Ukoliko jedan broj ima manje cifara od drugog, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih cifara. Tako se dobijaju dva niza binarnih cifara, označimo ih sa \(a_1, \ldots, a_k\) i \(b_1, \ldots b_k\). Zatim se za svaku poziciju \(i \in \{1, \ldots, k \}\) računa \(c_i\) pomoću sledećih pravila:
- Za
važi
- Za
važi
- Za
važi
- Za
važi
Niz binarnih cifara (koji možda ima vodeće nule) je binarni zapis rezultata, odnosno broja
.
Bitovska ekskluzivna disjunkcija između elemenata
definiše se kao
.
Comments