Fişierul intrare/ieşire:bulevard.in, bulevard.outSursăCCEX 2009
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/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.inbulevard.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content