.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » felinar

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
felinar


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
32MB / 1MB

A venit timpul Anarhiei în Oraşul Trist! Ca revoltă împotriva manifestărilor subculturale, vrei să pui Oraşul pe butuci. În urma unei descinderi ilegale la Primarie, ai „împrumutat” o hartă şi ţi-ai dat seama că există M străzi unidirecţionale între cele N intersecţii ale Oraşului Trist. Fiecare intersecţie are câte două felinare. Primul luminează o jumătate din fiecare stradă care pleacă din intersecţia respectivă, iar al doilea luminează jumătate din fiecare stradă care intră în intersecţie. De exemplu, prima jumătate a străzii dintre intersecţiile A şi B este luminată de primul felinar din intersecţia A, iar cea de-a doua jumătate este luminată de al doilea felinar din intersecţia B. Un felinar stins nu luminează deloc. O stradă este sigură doar atunci când e luminată în totalitate.

Cerinţă

În primul rând, trebuie să te asiguri că nicio stradă nu va fi complet luminată, astfel încât siguranţa cetăţenilor să fie redusă la minim. Dar acest obiectiv nu te mulţumeşte, aşa că în plus îţi doreşti un număr maxim de felinare aprinse, pentru a da o grea lovitură bugetului Primăriei din Oraşul Trist. Odată îndeplinite aceste condiţii, Revoluţia poate începe.

Date de intrare

Fişierul de intrare felinar.in conţine pe prima linie două numere naturale strict pozitive N şi M, reprezentând numărul de intersecţii şi numărul de străzi din Oraşul Trist. Pe fiecare din următoarele linii se află o pereche de numere naturale A şi B cuprinse între 1 şi N reprezentând o stradă care pleacă din intersecţia A şi ajunge în intersecţia B.

Date de ieşire

Fişierul de ieşire felinar.out va conţine pe prima linie un singur număr natural reprezentând numărul maxim de felinare ce pot fi aprinse. Pe următoarele N linii se vor afla numere cuprinse între 0 şi 3, cu semnificaţia următoare:
0 : ambele felinare din intersecţie sunt stinse;
1 : numai primul dintre felinarele din intersecţie este aprins;
2 : numai al doilea dintre felinarele din intersecţie este aprins;
3 : ambele felinare din intersecţie sunt aprinse.

Restricţii

1 ≤ N ≤ 8191
1 ≤ M ≤ 20000

Nu există străzi care să unească o intersecţie cu ea însăşi.
Pentru determinarea numărului maxim de felinare se acordă 40% din punctaj.

Exemple

felinar.infelinar.out
4 4 1 2 4 1 4 2 4 3 6 2 3 3 2

autor: Tiberiu Lucian Florea
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor