GInfo
Diverse
Revista
Concurs
Probleme
Homepage
Site vechi
Bacalaureat
Comunitate
Evaluator
Download
SETI@home
Grid.org
GInfoOnline
Articole
Publicare
Abonamente
Ed. a VI-a
Înscriere
Regulament
Probleme
Clasament
Lista
Propuneri
Soluții


www.trafic.ro - clasamente si statistici pentru site-urile romanesti




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.

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.

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.

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


  • 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


    CONCURS

    GInfo Online - ISSN 1583-6940
    Adresa redacției: Str. Universității nr. 8 ap. 8 Cluj-Napoca
    Telefon: 0264/592422
    Fax: 0265/266290
    E-mail: office@ginfo.ro
    Webmaster: webmaster@ginfo.ro