Sortari

sortari

==Include(page="template/taskheader" task_id="sortari")==

== include(page="template/taskheader" task_id="sortari") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| sortari.in | sortari.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="sortari") ==

==Include(page="template/raw")==
 
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.
 
h2. 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.
 
h2. 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.
 
h2. 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.
 
h2. Restrictii
 
. 1 <= N <= 17
 
. 1 <= M <= 600
 
h2. Exemplu
 
 
|sortari.in |sortari.out |
 
|2 |1 |
|4 6 |0 |
|1 2 | |
|2 3 | |
|3 4 | |
|1 2 | |
|2 3 | |
|1 2 | |
|3 2 | |
|2 3 | |
|1 2 | |
 
 
 
==Include(page="template/taskfooter" task_id="sortari")==