Cercuri
Limbajele de programare acceptate: Pascal, C și C++
Compilatoarele utilizate: Borland Pascal 7.0 și Borland C++ 3.1
Descrierea problemei
Un elf a desenat pe o lespede n cercuri.
Ceilalți trebuie să deseneze un număr total de m săgeți astfel încât fiecare săgeată să pornească de la un cerc și să ajungă la un alt cerc.
Pentru fiecare cerc a fost stabilit numărul
total al săgeților care trebuie să plece din cercul respectiv și
numărul total al săgeților care trebuie să ajungă în cercul respectiv.
În primul rând trebuie să se verifice dacă există posibilitatea desenării săgeților.
În cazul în care săgețile pot fi desenate, trebuie descrisă o modalitate de desenare.
Date de intrare
Prima linie a fișierului de intrare INPUT.TXT conține numărul n al cercurilor.
Pe cea de-a doua linie a fișierului se află numărul total m al săgeților care trebuie desenate.
Fiecare dintre următoarele n
linii conține câte două numere întregi, separate prin câte un spațiu.
Primul număr indică numărul săgeților care trebuie să plece de la
cercul corespunzător, iar al doilea număr indică numărul săgeților care
trebuie să ajungă la cercul corespunzător.
Prima dintre aceste n
linii corespunde cercului identificat prin 1, a doua linie corespunde
cercului identificat prin 2 și așa mai departe până la ultima linie
care corespunde cercului identificat prin n.
Suma primelor numere de pe aceste linii, precum
și suma numerelor aflate pe poziția a doua pe aceste linii, vor fi
întotdeauna egale cu m.
Date de ieșire
Prima linie a fișierului de ieșire OUTPUT.TXT trebuie să conțină mesajul DA în cazul în care există cel puțin o posibilitate de desenare a săgeților și mesajul NU în caz contrar.
În cazul în care săgețile pot fi desenate, fișierul va mai conține m linii pe care se vor afla câte două numere întregi, separate printr-un spațiu.
O astfel de linie va indica faptul că va fi
desenată o săgeată care va porni de la cercul identificat prin primul
număr și va ajunge la cercul identificat prin al doilea număr.
Restricții și precizări
numărul cercurilor care au fost desenate este cuprins între 1 și 100;
numărul săgeților care trebuie desenate este cuprins între 1 și 1000;
cercurile sunt identificate prin numere cuprinse între 1 și n;
poate fi desenată cel mult o săgeată care pornește de la un cerc identificat prin x și ajunge la un cerc identificat prin y;
d
acă se desenează o săgeată care pornește de la un cerc identificat prin x și ajunge la un cerc identificat prin y, atunci poate sau nu fi desenată o săgeată care pornește de la un cerc identificat prin y și ajunge la un cerc identificat prin x;
dacă există mai multe soluții, atunci poate fi aleasă oricare dintre ele.
Exemplu
INPUT.TXT
4
5
1 1
2 1
2 1
0 2
OUTPUT.TXT
DA
1 2
2 3
3 1
2 4
3 4
Timp de execuție: 2 secunde/test
|