Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | light.in, light.out | Sursă | ad-hoc |
| Autor | Radu Toma | Adăugată de |  Toma Radu •tm_radu |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 5596 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Light
Avi a ajuns primar in orasul sau natal, iar o prima problema cu care se confrunta este iluminatul public. Strada principala poate fi considerata ca fiind o axa cu originea in punctul O. De-a lungul soselei exista <b>N</b> obiective principale, despre care Avi stie ca se afla la distanta <b>a</b> de punctul O si se intind pe o lungime <b>b</b>. Firma EPT (Electricitate Pentru Tonti) i-a facut o oferta : el va primi maxim <b>nr</b> stalpi de iluminare pentru acelasi pret, si cu aceeasi raza de iluminat, oricare o va cere primarul. Fiecare stalp poate ilumina o portine de lungime <b>R</b> numar intreg, dar intr-un mod ciudat : acesta poate ilumina <b>R1</b> unitati de drum in stanga sa si <b>R2</b> unitati in dreapta sa, cat timp cat <b>R1</b>+<b>R2</b> = <b>R</b>. <b>R1</b> si <b>R2</b> pot fi reglate odata cu amplasarea stalpului, insa <b>R</b> este fix din fabrica. Stiind ca o raza mai mare de iluminat determina un cost mai mare in timp, Avi va roaga sa determinati raza minima pentru care el poate asigura iluminatul obiectivelor principale.
<b>Cerinta</b>
Cunoscand pozitiile de inceput si distanta pe care se intind a fiecarui obiectiv, determinati raza <b>R</b> minima ce o pot avea stalpii pentru a putea ilumina complet fiecare obiectiv, precum si numarul minim de stalpi necesari.
Date de intrare
Fisierul de intrare light.in va contine pe prima linie numarul <b>N</b> de obiective si <b>nr</b> - numarul maxim de stalpi, iar pe urmatoarele <b>N</b> linii cate 2 valori, <b>a[i]</b> - distanta pana in punctul O al obiectivului i, si <b>b[i]</b> - lungimea sa.
Date de iesire
In fisierul de iesire light.out se vor afisa pe o singura linie 2 valori, <b>Rmin</b> si <b>nrmin</b>, reprezetand portiunea iluminata de fiecare stalp, precum si numarul minim de stalpi necesari.
Restrictii
- 1 ≤ N ≤ 100.000
- 0 ≤ a[i] ≤ 1.000.000.000
- 1 ≤ b[i] ≤ 1.000.000.000
- 1 ≤ nr ≤ 1.000.000
Exemplu
| light.in | light.out |
|---|---|
| 4 4 1 4 6 4 16 2 15 2 | 3 4 |
| 4 3 1 4 6 4 16 2 15 2 | 4 3 |
Explicatie
In primul caz, stalpul 1 va ilumina portiunea (1, 4), stalpul 2 portiunea (5, 8), stalpul 3 portiunea (9, 12), iar stalpul 4 portiunea (15, 18). In al doilea, stalpul va ilumina portiunea (1, 5), stalpul 2 portiunea (6, 10), iar stalpul 3 portiunea (15, 19);
