Fişierul intrare/ieşire:sortnet.in, sortnet.outSursăLot 2002
AutorMihai PatrascuAdăugată de
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

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 2N 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).

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).

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.

Restrictii si precizari

  • 2 ≤ N ≤ 20 si N par
  • 0 ≤ M ≤ 32

Exemplu

sortnet.insortnet.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content