Fişierul intrare/ieşire:muzeu.in, muzeu.outSursă.campion 2009
AutorProf. Emanuela CerchezAdăugată dedanpatrickDan Patrick Cristian danpatrick
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Muzeu(clasa a 6-a)

Muzeul de ştiinţe naturale de la noi din oraş oferă posibilitatea organizării lecţiilor de biologie în muzeu. Astăzi au fost programate n grupuri de elevi, astfel încât să nu existe în muzeu două grupuri în acelaşi timp. Grupurile sunt numerotate de la 1 la n, în ordinea în care sosesc la muzeu. Toţi elevii dintr-un grup vin împreună şi pleacă împreună, la terminarea lecţiei.
La intrarea în muzeu există k dulăpioare în care elevii îşi pot depozita obiectele personale pe durata vizitării muzeului.
Dimineaţa toate cele k dulăpioare sunt încuiate. Când un elev vine la lecţie, primeşte cheia de la un dulap, îşi depozitează obiectele personale în dulap, iar la plecare îşi la obiectele din dulap şi predă cheia. Unii dintre elevi încuie dulapul înainte de a preda cheia, alţii îl lasă deschis.
Personalul de la muzeu au observat că în grupul i (1≤i≤n) ai elevi încuie dulapul, în timp ce bi elevi lasă dulapul deschis.
Personalul muzeului doreşte să distribuie cheile în aşa fel încât la sfârşitul zilei să rămână cât mai multe dulapuri încuiate.

Cerinta

În ipoteza că personalul muzeului distribuie cheile optimal, să se determine care este numărul maxim de dulapuri care rămân închise la sfârşitul zilei.

Date de intrare

Fişierul de intrare muzeu.in conţine pe prima linie două numere naturale separate prin spaţiu n k, cu semnificaţia din enunţ.
Urmează n linii. Pe linia i+1 sunt scrise două numere naturale ai bi cu semnificaţia că în grupul i ai elevi închid dulapul, iar bi elevi lasă dulapul deschis.

Date de ieşire

Fişierul de ieşire muzeu.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul maxim de dulapuri care rămân închise la sfârşitul zilei.

Restricţii

  • 1 ≤ n ≤ 100
  • 1 ≤ k ≤ 1000
  • 0 ≤ ai ≤ k
  • 0 ≤ bi ≤ k
  • ai+bi ≤ k

Exemplu

muzeu.inmuzeu.out
2 4
1 2
1 1
3

Explicaţie


Există 4 dulapuri. La muzeu vin două grupuri de elevi. În primul grup elevul 1 încuie dulapul 1, iar elevii 2 şi 3 lasă deschise dulapurile 2 şi 3.
În al doilea grup, elevul 1 primeşte cheia de la dulapul 2 pe care îl încuie, iar elevul 2 primeşte cheia de la dulapul 3 pe care îl lasă deschis.
Prin urmare dulapurile 1, 2, 4 rămân închise.

Trebuie sa te autentifici pentru a trimite solutii. Click aici