==Include(page="template/taskheader" task_id="sortnet")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
Link: [2]Edit-Time-Data
 
Sortnet
 
 
 
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.
 
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
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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 corect, 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
 
. 2 -L- N -L- 20 si N par
 
. 0 -L- M -L- 32
 
h2. Exemplu
 
sortnet.in sortnet.out Explicatie
4 2 14 exemplul este cel din figura; 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
 
<1,3> <2,4>
 
<3,4> <1,2>
 

==Include(page="template/taskheader" task_id="sortnet")==
 
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.
 
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!
 
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 &le; N &le; 20$ si $N$ par
* $0 &le; M &le; 32$
 
h2. Exemplu
 
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")==

References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/sortnet/enunt_files/filelist.xml
2. file:///home/eval/eval/www/infoarena/docs/arhiva/sortnet/enunt_files/editdata.mso
==Include(page="template/taskfooter" task_id="sortnet")==

872