== include(page="template/taskheader" task_id="sortnet") ==
==Include(page="template/taskheader" task_id="sortnet")==
Poveste ...
O retea de sortare este formata din $N$ linii de date, numerotate de la $1$ la $N$, legate prin comparatori. Pe o linie de date circula valori numerice; initial $N$ valori oarecare sunt introduse in retea si se asteapta ca reteaua sa furnizeze la iesire o permutare a acestor numere. O retea de sortare perfecta va furniza la iesire valorile in ordine crescatoare.
h2. Cerinta
Comparatorii sunt plasati intre doua linii de date cu scopul de a aseza in ordine crescatoare cele doua valori. Un comparator poate lega oricare doua linii $A$ si $B$, cu $A < B$; un astfel de comparator este notat simbolic cu <{$A$},{$B$}> sau grafic cu un segment vertical intre cele doua linii de date. Notatia grafica determina univoc comparatorul. Imaginati-va un segment care uneste liniile $1$ si $3$; acesta reprezinta comparatorul <{$1$},{$3$}>, deoarece <{$3$},{$1$}> nu poate fi un comparator (vezi definitia de mai sus). In aceasta problema, numarul de linii de date va fi intotdeauna par. Un ciclu de sortare este format din $N/2$ comparatori, astfel incat fiecare linie este legata la un singur comparator. O retea de sortare completa de adancime $M$ este o retea de sortare formata din $M$ cicli de sortare.
Un exemplu valoreaza cat 1000 de cuvinte:
...
!problema/sortnet?sortnet.gif!
h2. Restrictii
Reteaua din figura are $4$ linii de date si $2$ cicli de sortare. Se observa ca aceasta retea de sortare nu este perfecta. Desi sorteaza corect datele din figura (secventa {$7$},{$8$},{$7$},{$3$}), ea nu va sorta corect secventa {$1$},{$3$},{$2$},{$9$}.
...
h2. Cerinta
Se poate demonstra ca daca o retea sorteaza corect orice intrare formata numai din numerele $0$ si $1$, ea va sorta corect orice secventa de numere. Are deci sens sa spunem ca o retea este cu atat mai buna, cu cat sorteaza corect mai multe intrari formate din numerele $0$ si $1$. Exista $2^N^$ astfel de intrari; scrieti un program care determina cate dintre aceste intrari posibile sunt sortate corect de o anumita retea (prin sortate corecta, intelegem ca la iesire toate numerele de zero apar inaintea celor de unu).
h2. Date de intrare
...
Pe prima linie a fisierului de intrare $sortnet.in$ sunt scrise doua numere intregi $N$ si $M$, reprezentand numarul de linii de date, respectiv numarul de cicli de sortare. Pe fiecare dintre urmatoarele $M$ linii sunt reprezentati $N/2$ comparatori, in formatul <{$A$},{$B$}>, cu $A$ si $B$ numere intregi intre $1$ si $N$, $A < B$. Nici un numar nu se va repeta in descrierea unui ciclu de sortare (fiecare linie este legata la exact un comparator in fiecare ciclu).
h2. Date de iesire
...
Fisierul $sortnet.out$ va contine numarul de intrari formate numai din numerele $0$ si $1$, care sunt sortate corect de catre reteaua considerata.
h2. Restrictii si precizari
* $2 ≤ N ≤ 20$ si $N$ par
* $0 ≤ M ≤ 32$
h2. Exemplu
| sortnet.in | sortnet.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. sortnet.in|_. sortnet.out|
|4 2
<1,3> <2,4>
<3,4> <1,2>
|14|
_Explicatie_: Exemplul corespunde figurii; cele doua secvente formate din cifre de $0$ si $1$ care nu sunt sortate corect sunt {$0$},{$1$},{$0$},{$1$} si {$1$},{$0$},{$1$},{$0$}.
== include(page="template/taskfooter" task_id="sortnet") ==
==Include(page="template/taskfooter" task_id="sortnet")==
