==Include(page="template/taskheader" task_id="ben")==
==Include(page="template/raw")==
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.
h2. 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.
h2. 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.
h2. 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.
h2. Restrictii
. 0 < N <= 30 000, dar pentru 70% din teste N <= 300
o Timpii de sosire si plecare vor fi numere intregi din intervalul [1, 30 000]
o Nu va exista o masina care soseste in momentul pleacarii altei masini
o 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.
o 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
o Clientilor nu le place sa astepte asa ca trebuie sa va asigurati ca exista cel putin o pompa libera la sosirea fiecaruia in benzinarie
o Atentie! Numarul Sse va afisa modulo 32173
Exemple
|ben.in|ben.out|Explicatii |
|4 |2 4 |Numarul minim de pompe de alimentare este 2. |
| | | |
|1 4 | |Cele 4 modalitati de servire ale clientilor sunt: |
| | | |
|5 7 | |1, 1, 1, 2 (prima modalitate) |
| | | |
|8 10 | |1, 1, 2, 2 (a doua) |
| | | |
|2 7 | |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. |
==Include(page="template/taskheader" task_id="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.
h2. 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.
h2. 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.
h2. 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$}.
h2. 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$
h2. Exemple
table(example). |_. ben.in |_. ben.out |
| 4
1 4
5 7
8 10
2 7
| 2 4 |
h3. 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.
==Include(page="template/taskfooter" task_id="ben")==
==Include(page="template/taskfooter" task_id="ben")==
