Fişierul intrare/ieşire:sortari.in, sortari.outSursăpreONI 2003
AutorVlad DascaluAdăugată de
Timp execuţie pe test0.45 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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

Restrictii si precizari

  • 1 ≤ N ≤ 17
  • 1 ≤ M ≤ 600

Exemplu

sortari.insortari.out
2
4 6
1 2
2 3
3 4
1 2
2 3
1 2
3 2
2 3
1 2
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content