Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sortari.in, sortari.out | Sursă | preONI 2003 |
| Autor | Vlad Dascalu | Adăugată de | |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Sortari
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
Sortari
Ion si Vasile se joaca cu numerele. Ei au un sir de N numere naturale si decid sa faca asupra lui M operatii. O operatie consta in alegerea a doua pozitii i si j astfel incat i <= j si interschimbarea valorilor lor in cazul in care valoarea indicata de i este mai mare decat cea indicata de j.
Cerinta
Scrieti un program care determina (pentru mai multe subteste) daca operatiile alese de Ion si Vasile vor sorta crescator orice sir de N numere, indiferent de asezarea lor initiala.
Date de Intrare
Prima linie a fisierului de intrare sortari.in contine numarul T de teste, in continuare fiind descris fiecare test. Pe prima linie a fiecarui test vor exista 2 numere N si M , reprezentand numarul de elemente din sirul lor, respectiv numarul de operatii alese. Urmeaza apoi M linii, pe fiecare fiind cate 2 numere ai,bi descriind pozitiile alese pentru operatia respectiva.
Date de Iesire
In fisierul sortari.out vor exista T linii, fiecare continand valoarea 1 in cazul in care operatiile alese de Ion si Vasile sorteaza crescator orice sir de numere de lungime N sau 0 in caz contrar.
Restrictii
. 1 <= N <= 17
. 1 <= M <= 600
Exemplu
| sortari.in | sortari.out |
| 2 | 1 |
| 4 6 | |
| 1 2 | |
| 2 3 | |
| 3 4 | |
| 1 2 | |
| 2 3 | |
| 1 2 | |
| 3 2 | |
| 2 3 | |
| 1 2 | |
