Fişierul intrare/ieşire:felinare.in, felinare.outSursăONI 2007, clasele 11-12
AutorTiberiu-Lucian FloreaAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.05 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Felinare

A venit timpul Anarhiei in Orasul Trist! Ca revolta impotriva manifestarilor subculturale, vrei sa pui Orasul pe butuci. In urma unei descinderi ilegale la Primarie, ai "imprumutat" o harta si ti-ai dat seama ca exista M strazi unidirectionale intre cele N intersectii ale Orasului Trist. Fiecare intersectie are cate doua felinare. Primul lumineaza o jumatate din fiecare strada care pleaca din intersectia respectiva, iar al doilea lumineaza jumatate din fiecare strada care intra in intersectie. De exemplu, prima jumatate a strazii dintre intersectiile A si B este luminata de primul felinar din intersectia A, iar cea de-a doua jumatate este luminata de al doilea felinar din intersectia B. Un felinar stins nu lumineaza deloc. O strada este sigura doar atunci cand e luminata in totalitate.

Cerinta

In primul rand, trebuie sa te asiguri ca nicio strada nu va fi complet luminata, astfel incat siguranta cetatenilor sa fie redusa la minim. Dar acest obiectiv nu te multumeste, asa ca in plus iti doresti un numar maxim de felinare aprinse, pentru a da o grea lovitura bugetului Primariei din Orasul Trist. Odata indeplinite aceste conditii, Revolutia poate incepe.

Date de intrare

Fisierul de intrare felinare.in contine pe prima linie doua numere naturale strict pozitive N si M, reprezentand numarul de intersectii si numarul de strazi din Orasul Trist. Pe fiecare din urmatoarele linii se afla o pereche de numere naturale A si B cuprinse intre 1 si N reprezentand o strada care pleaca din intersectia A si ajunge in intersectia B.

Date de iesire

Fisierul de iesire felinare.out va contine pe prima linie un singur numar natural reprezentand numarul maxim de felinare ce pot fi aprinse. Pe urmatoarele N linii se vor afla numere cuprinse intre 0 si 3, cu semnificatia urmatoare:

  • 0 : ambele felinare din intersectie sunt stinse;
  • 1 : numai primul dintre felinarele din intersectie este aprins;
  • 2 : numai al doilea dintre felinarele din intersectie este aprins;
  • 3 : ambele felinare din intersectie sunt aprinse.

Restrictii

  • 1 ≤ N ≤ 8191
  • 1 ≤ M ≤ 20 000
  • Nu exista strazi care sa uneasca o intersectie cu ea insasi.
  • Pentru determinarea numarului maxim de felinare se acorda 40% din punctaj.

Exemplu

felinare.infelinare.out
4 4
1 2
4 1
4 2
4 3
6
2
3
3
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content