Avem N
bile (numerotate de la 1 la N),
oricare doua bile avand greutati diferite. Pentru a descoperi bila cu greutatea
mediana (deci cea de a (N+1)/2-a
bila, in ordinea greutatilor) putem utiliza o balanta cu doua platane. Putem
plasa cate o bila pe fiecare platan si astfel putem afla care dintre cele doua
bile este mai grea. Ca urmare a rezultatelor obtinute in urma unui set de astfel
de cantariri, putem elimina unele dintre bile, despre care putem afirma cu siguranta
ca nu au greutatea mediana.
De exemplu sa consideram N=5
bile, intre care s-au efectuat M=4
cantariri, obtinand urmatoarele rezultate:
Bila 2 este mai grea decat bila 1.
Bila 4 este mai grea decat bila 3.
Bila 5 este mai grea decat bila 1.
Bila 4 este mai grea decat bila 2.
Din rezultatele de mai sus, desi nu putem determina exact bila cu greutatea
mediana, putem afirma ca bila 1 si bila 4 nu pot avea greutatea mediana, deoarece
bilele 2, 4, 5 sunt mai grele decat bila 1, iar bilele 1, 2, 3 sunt mai usoare
decat bila 4. Prin urmare putem elimina aceste doua bile.
Cerinta
Scrieti un
program care sa determine pe baza unui set de cantariri dat numarul de bile
care nu pot avea greutatea mediana.
Date de intrare
Fisierul
de intrare bile1.in contine pe
prima linie numarul natural N
reprezentand numarul de bile si numarul natural M
reprezentand numarul de cantariri, separate printr-un spatiu. Fiecare dintre
urmatoarele M linii contine doua
numere naturale cuprinse intre 1
si N cu semnificatia "bila
corespunzatoare primului numar este mai grea decat bila corespunzatoare celui
de al doilea numar".
Date de iesire
Fisierul
de iesire bile1.out contine o
singura linie pe care se afla numarul de bile care nu pot avea greutatea mediana.
Restrictii
N
numar natural impar, 0<N<=300
M<=5000
Este posibil ca in fisierul de intrare sa existe mai multe cantariri pentru
aceeasi pereche de bile; evident la fiecare cantarire obtineti acelasi rezultat.
Exemple
bile1.in
bile1.out
5 4
2 1
4 3
5 1
4 2
2
prof. Emanuela
Cerchez
Liceul de Informatica "Grigore Moisil" Iasi