Fişierul intrare/ieşire:ben.in, ben.outSursăStelele Informaticii 2005, clasele 9-10
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Ben

La o benzinarie sosesc intr-o zi N masini pentru a se alimenta. Pentru fiecare masina se cunoaste momentul sosirii si momentul plecarii din benzinarie, intervalul de timp dintre sosire si plecare fiind utilizat exclusiv pentru alimentare. O pompa de benzina se poate utiliza pentru alimentarea unei singure masini la un moment dat (ea poate sa alimenteze mai multe masini dar nu in acelasi timp). Alimentarea unei masini incepe exact in momentul sosirii ei in benzinarie si se termina exact in momentul plecarii, fiind utilizata o singura pompa pe tot timpul parcarii sale in benzinarie.

Cerinta

Stiind informatiile despre sosirile si plecarile celor N clienti, aflati K reprezentand numarul minim de pompe de benzina necesare servirii tuturor clientilor. Se cere si numarul de modalitati distincte de servire a clientilor utilizand exact K pompe de alimentare.

Date de Intrare

In fisierul ben.in se afla pe prima linie un numar N reprezentand numarul de clienti. Urmeaza N linii fiecare continand doua numere, A si B (A<B), separate printr-un spatiu reprezentand timpul de sosire respectiv timpul de plecare al unui client.

Date de Iesire

Fisierul de iesire ben.out va contine o singura linie pe care se vor afla doua numere intregi K si S reprezentand numarul minim de pompe de alimentare si numarul de modalitati de servire a clientilor folosind exact K pompe de alimentare. Numarul S va fi afisat modulo 32173.

Restrictii

  • 0 ≤ N ≤ 30 000, dar pentru 70% din teste N ≤ 300
  • Timpii de sosire si plecare vor fi numere intregi din intervalul [1, 30 000]
  • Nu va exista o masina care soseste in momentul pleacarii altei masini
  • Daca primul numar din fisierul de iesire este corect veti primi 6 puncte pe acel test iar daca sunt corecte ambele numere veti primi 10 puncte. Nu se vor acorda puncte daca este corect numai cel de-al doilea numar.
  • Doua modalitati de servire a clientilor se considera diferite daca exista cel putin un client care nu a fost servit la aceeasi pompa in cele doua modalitati
  • Clientilor nu le place sa astepte asa ca trebuie sa va asigurati ca exista cel putin o pompa libera la sosirea fiecaruia in benzinarie
  • Atentie! Numarul se va afisa modulo 32173

Exemple

ben.inben.out
4
1 4
5 7
8 10
2 7
2 4

Explicatii

Numarul minim de pompe de alimentare este 2. Cele 4 modalitati de servire ale clientilor sunt:
1, 1, 1, 2 (prima modalitate)
1, 1, 2, 2 (a doua)
2, 2, 1, 1 (a treia) 
2, 2, 2, 1 (a patra)
Fiecare numar reprezinta indicele pompei la care s-a alimentat fiecare client, pastrand ordinea acestora din fisierul de intrare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content