Rezolvare PBinfo #4490

Pentru un număr natural n dat, codul Gray(n) se referă la ordonarea tuturor șirurilor binare de lungime n, astfel încât oricare două șiruri alăturate să difere prin exact un bit. Astfel codul Gray(1) constă din două secvențe binare de lungime 1:
0
1
Codul Gray(2) este:
00
01
11
10
Pentru obținerea codului Gray(3) se procedează astfel: Se scrie codul Gray(2), apoi din nou Gray(2), dar cu șirurile scrise în ordine inversă:
00
01
11
10
------
10
11
01
00
Apoi la primele patru secvențe li se adaugă la început bitul 0, iar la ultimele patru li se adaugă la început un bit de 1:
000
001
011
010
------
110
111
101
100

Procedeul continuă până când obținem codul Gray(n). Fiind în total 2n secvențe binare în codul Gray(n), le numerotăm cu numere de la 0 la 2n-1. Se creează astfel o corespondență între orice șir binar din codul Gray și un șir binar reprezentând scrierea unui număr natural în baza 2. De exemplu, pentru n = 3:

Număr Baza_2 Cod_Gray
0 000 000
1 001 001
2 010 011
3 011 010
4 100 110
5 101 111
6 110 101
7 111 100

Cerința

Dată o secvență de n biți reprezentând un cod binar, să se determine secvența asociată din codul Gray(n), apoi dat un șir de n biți reprezentând o secvență a codului Gray(n), să se determine codul binar asociat.

Date de intrare

Se citește de la tastatură un număr n, apoi, fără spații, de pe a doua linie un șir b1 b2 … bn de cifre binare, iar de pe a treia linie un șir binar g1 g2 … gn reprezentând o secvență din codul Gray(n).

Date de ieșire

Programul va afișa pe ecran pe prima linie secvența din codul Gray(n) asociată lui b1 b2 … bn, iar pe a doua linie secvența binară asociată secvenței g1 g2 … gn a codului Gray(n).

Restricții și precizări

• 1 ≤ n ≤ 500

Exemplu:

Intrare

3
011
111

Ieșire

010
101

Explicație

Pentru codul binar 011 avem corespunzătoare secvența 010 din codul Gray(3), iar secvenței 111 din codul Gray(3) îi corespunde șirul binar 101.