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.

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

Ú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.

3

Enginn

6

Gunnar

5

1