sortari

Sortari

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

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

Poveste ...

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

...
 
h2. Restrictii
 
...

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 {$a{~i~},b{~i~}$}, descriind pozitiile alese pentru operatia respectiva.

h2. Date de iesire

...

In fisierul de iesire $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 si precizari
 
* $1 ≤ N ≤ 17$
* $1 ≤ M ≤ 600$

h2. Exemplu

| sortari.in | sortari.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. sortari.in|_. sortari.out|
|2
4 6
1 2
2 3
3 4
1 2
2 3
1 2
3 2
2 3
1 2
|1
0|

== include(page="template/taskfooter" task_id="sortari") ==

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

668