Pentru a fi siguri ca aprindem becul trebuie in cel mai rau caz sa trecem prin toate configuratiile apasat/ne-apasat ale intrerupatoarelor. Pentru a schimba starea curenta trebuie sa apasam cel putin un buton, deci in cazul cel mai defavorabil va trebui sa facem cel putin $2^n^ - 1$ apasari. Codul Gray ne da o posibilitate de a trece prin toate configuratiile trecand de la una la alta prin o apasare de buton, rezolvandu-ne problema.

h2(#matrix). Problema 3: _Matrix_ ( acm.sgu.ru - 249)

h2(#matrix). Problema 3: '_Matrix_':http://acm.sgu.ru/problem.php?contest=0&problem=249 (SGU)

Trebuie sa aranjati numerele de la $0$ la $2^(n + m)^ - 1$ intr-o matrice cu $2^n^$ randuri si $2^m^$ coloane. De asemenea, numerele care sunt situate in celule adiacente pe verticala sau orizontala trebuie sa difere prin exact un bit in reprezentarea lor binara. Matricea este ciclica, adica pentru fiecare rand celula cea mai din stanga se considera invecinata cu cea mai din dreapta, de asemenea pentru fiecare coloana celula cea mai de sus se considera invecinata cu celula cea mai de jos. La intrare se dau numerele $n$ si $m$ ( $0 < n, m; n + m <= 20$ ). Trebuie sa afisati o asemenea matrice. De exemplu daca $n = 1$ si $m = 1$ o matrice ar fi
( $0$ $2$ )

Este evident ca orice doua numere adiacente in matrice sunt diferite in reprezentarea binara prin exact un bit. In concurs limita de timp era foarte stransa si trebuia folosita functia prezentata anterior. Deci pe linia $i$, coloana $j$ a matricei scriem numarul (binToGray(i) << M) | binToGray(j).

h2(#divizori). Problema 4: _Divizori_

h2(#divizori). Problema 4: '_Divizori_':problema/divizori

Vom considera un numar natural $N$. In sirul $A$ vom aseza toti divizorii lui $N (2 <= N <= 2.000.000.000)$. Se cere sa se permute elementele sirului $A$ astfel incat pentru oricare doua elemente consecutive $A[i]$ si $A[i+1]$ sa avem fie $A[i] = A[i+1] * p$, fie $A[i+1] = A[i] * p$ ( $p$ numar prim oarecare). Valoarea $p$ poate diferi de la o pereche de elemente la alta. De exemplu, pentru $N = 12$ o posibila solutie ar fi $1, 2, 3, 4, 12, 6, 3$.

Complexitatea finala a solutiei este $O(T)$ unde $T$ reprezinta numarul de divizori ai lui $N$.

h2(#sortnet). Problema 5: _Sortnet_ (Mihai Patrascu, lot 2002)

h2(#sortnet). Problema 5: '_Sortnet_':problema/sortnet (Lot 2002)

O retea completa de sortare este o retea de sortare cu $N$ fire de adancime $D$ ce are $D * (N/2)$ comparatori. Amintim principiul $0-1$ care spune ca o retea de sortare sorteaza orice $N$ numere daca aceasta sorteaza orice secventa de $N$ numere $0-1$. Problema noastra cere sa se determine cate astfel de secvente de $0-1$ nu sunt sortate corect.

h2(#biblio). Bibliografie

* [1] D.E.Knuth TAOC Prefascicle 2A
* [2] W.H. Press et. all. Numerical Recipies in C, Cambridge University Press
* [3] 'http://en.wikipedia.org/wiki/Gray_code':http://en.wikipedia.org/wiki/Gray_code

# D.E.Knuth TAOC Prefascicle 2A
# W.H. Press et. all. Numerical Recipies in C, Cambridge University Press
# 'Gray code, wikipedia':http://en.wikipedia.org/wiki/Gray_code