Start

2017-03-18 02:00 AKDT

Delta 2017

End

2017-03-18 08:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1282 days 10:53:42

Time elapsed

6:00:00

Time remaining

0:00:00

Problem D
XORsistinn

Presturinn Gunnar fékk dularfull skilaboð í pósti í gær þar sem stóð að eitt af sóknarbörnum hans væri mögulega andsetið. Á bakhliðinni var búið að skrifa ,,Þú ert okkar eina von XORsist!". Gunnar var nefnilega líka særingamaður og hefur mikla reynslu af því að bæla í burtu púka og djöfla.

Hann ákvað að skrifa niður nöfnin á öllum í sókninni sinni og endaði með nöfn númeruð frá $1$ upp í $N$. Seinna fattaði hann að ef hann myndi taka XOR af öllum tölum frá $1$ upp í $N$ myndi það gefa honum upplýsingar um hver væri andsetinn; ef talan er $0$ þá er enginn andsetinn, ef hún er á bilinu $1$ og upp í $N$ þá er það manneskjan á listanum hans sem passar við þá tölu. Ef hún er hinsvegar stærri en $N$ þá er það Gunnar sjálfur sem er andsetinn og þá erum við öll í vanda!

Útskýring á XOR

XOR, venjulega táknuð með $~ \hat{}~ $ í forritunarmálum, er aðgerð sem tekur tvær tölur og skilar nýrri tölu. Aðgerðin er framkvæmd á tölurnar tvær á tvíundarformi (e. binary), bita fyrir bita. Eftirfarandi tafla sýnir hvernig nýr biti er reiknaður út frá samsvarandi bitum í tölunum tveimur.

A

B

A XOR B

1

1

0

1

0

1

0

1

1

0

0

0

Tökum dæmi. Talan $1337$ í binary er 10100111001 og talan $1993$ í binary er 11111001001.

1337

1

0

1

0

0

1

1

1

0

0

1

1993

1

1

1

1

1

0

0

1

0

0

1

1337 XOR 1993

0

1

0

1

1

1

1

0

0

0

0

Útkoman er 01011110000 sem er talan $752$.

Inntak

Fyrsta og eina línan inniheldur heiltölu $N$, hversu mörg sóknarbörn eru í sókninni hans Gunnars.

Úttak

Prentið út númerið á sóknarbarninu sem er andsetið, Enginn ef talan er $0$ og Gunnar ef talan er stærri en $N$.

Útskýring á sýnidæmum

Í fyrsta sýnidæminu er $N = 3$. Ef við reiknum XOR af öllum tölum frá $1$ upp í $N$, þá fáum við $(1\textrm{ XOR }2)\textrm{ XOR }3 = 0$. Það er því enginn andsetinn, og svarið er Enginn.

Í öðru sýndæminu er $N = 6$. Ef við reiknum XOR af öllum tölum frá $1$ upp í $6$, þá er útkoman $7$. Gunnar er því andsetinn, og svarið er Gunnar.

Í þriðja sýndæminu er $N = 5$. Ef við reiknum XOR af öllum tölum frá $1$ upp í $5$, þá er útkoman $1$. Barn númer $1$ er því andsetið, og svarið er 1.

Stigagjöf

Lausnin mun verða prófuð á miserfiðum inntaksgögnum, og er gögnunum skipt í hópa eins og sýnt er í töflunni að neðan. Lausnin mun svo fá stig eftir því hvaða hópar eru leystir.

Hópur

Stig

Inntaksstærð

1

50

$ 1 \le N \le 1000$

2

50

$ 1 \le N \le 10^{18}$

Sample Input 1 Sample Output 1
3
Enginn
Sample Input 2 Sample Output 2
6
Gunnar
Sample Input 3 Sample Output 3
5
1