Nosaukums
Xor palindroms (xorpal)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
64%

Definīcija

Gudrinieku ciema skolēnam Paulim šodien ir kontroldarbs matemātikā. Vienā uzdevumā viņam ir dots nenegatīvs vesels skaitlis x binārajā pierakstā un prasīts atrast vismazāko tādu nenegatīvu veselo skaitli y, ka skaitlis z = xor y ir palindroms, ja to arī uzraksta binārajā pierakstā.

Paulim izdevās izzagties uz tualeti un nosūtīt izziņu ar šo uzdevumu Jums – tā kā jums ir dators, palīdziet Paulim atrisināt uzdevumu!


Ievaddatu raksturojums

Pirmajā rindā dots viens naturāls skaitlis n (1 ≤ n ≤ 105), ciparu skaits binārajā pierakstā. Nākamajā rindā dota virkne no simboliem 0 un 1 garumā n, x pierakstīts binārajā skaitīšanas sistēmā. Garantēts, ka pierakstā nav vadošo nuļļu.


Izvaddatu raksturojums

Izvadiet prasīto skaitli y binārajā pierakstā bez vadošajām nullēm.


Piezīmes

Diviem bināriem cipariem a un b operācija xor tiek definēta šādi:

0 xor 0 = 0

0 xor 1 = 1

1 xor 0 = 1

1 xor 1 = 0

Pieņemsim, ka skaitļi x un y binārajā pierakstā ir a1a2...an un b1b2...bn (iespējams, ar vadošajām nullēm). Par x xor y sauc tādu skaitli, kura binārais pieraksts ir c1c2...cn, kur ci = ai xor bi visiem i no 1 līdz n

 

Simbolu virkni sauc par palindromu, ja to lasa vienādi gan no kreisās, gan no labās puses. Piemēram, 10101 un 1001 ir palindromi, bet 011 – nav.


Paraugdati

Stdin
8
10111011
Stdout
110

Stdin
3
101
Stdout
0

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.