| Fişierul intrare/ieşire: | bulevard.in, bulevard.out | Sursă | CCEX 2009 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bulevard
Pe un mare bulevard din localitatea CCEX se intampla numeroase incidente rutiere. Datorita experientei pe care a dobandit-o, politia locala poate preciza timpii la care au loc frecvent incidentele. Astfel, politia dispune de N timpi, numere naturale, la care se stie ca exista un grad crescut de pericol. Politia locala a angajat 2 noi politisti si doreste sa ii trimita pe teren, pentru a supraveghea traficul. Cei doi politisti au fiecare un timp de lucru de T unitati.
Sa se determine cand trebuie sa isi inceapa programul fiecare dintre cei doi politisti astfel incat programul de lucru al celor doi sa cuprinda un numar maxim de incidente din cele date.
Date de intrare
Fisierul de intrare bulevard.in conţine pe prima linie un număr natural N care reprezintă numărul de timpi la care poate avea loc un incident. Urmatoarea linie contine exact N numere naturale, in ordine crescatoare, despartite prin cate un spatiu, reprezentand timpii la care au loc incidentele. Cea de a treia linie si ultima din fisier contine numarul natural T, timpul de lucru pentru fiecare politist.
Date de ieşire
Fisierul de iesire bulevard.out va contine o singura linie pe care va fi scris numarul maxim de incidente ce pot fi acoperite prin programul de lucru al politistilor. A doua linie contine doua numere naturale, reprezentand timpii la care cei doi politisti incep programul. Daca sunt mai multe solutii, se va afisa cea in care primul numar este cat mai mic. Daca si in acest caz exista mai multe solutii, se va afisa cea in care suma celor doua numere este minima.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ T ≤ 1 000 000
- Timpii la care au loc incidentele sunt mai mici decat 100 000 001
- Pot exista doua incidente care sa aiba loc in acelasi timp
- Politistii nu isi pot incepe programul mai devreme de timpul 0
Exemplu
| bulevard.in | bulevard.out |
|---|---|
| 8 1 3 8 12 19 22 25 36 7 | 6 1 18 |
Explicaţie
Primul politist lucreaza in perioada [1, 8], iar al doilea politist in perioada [18, 25]. Astfel, sunt supravegheate evenimentele de la timpii 1, 3, 8, 19, 22 si 25.
