Inverseaza reviziile

Diferente pentru problema/light intre reviziile #3 si #10

Diferente intre #2 si #3

Diferente intre titluri:

light

Light

Diferente intre continut:

== include(page="template/taskheader" task_id="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.

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 $N$ obiective principale, iar despre al $i$-lea obiectiv Avi stie ca se afla la distanta $a{~i~}$ de punctul O si se intind pe o lungime $b{~i~}$. Firma EPT (Electricitate Pentru Tonti) i-a facut o oferta: el va primi maxim $nr$ stalpi de iluminare pentru acelasi pret, si cu aceeasi raza de iluminat, oricare o va cere primarul. Fiecare stalp poate ilumina o portiune de lungime $R$ numar intreg, dar intr-un mod ciudat: acesta poate ilumina $R1$ unitati de drum in stanga sa si $R2$ unitati in dreapta sa, cat timp $R1+R2$ = $R$. $R1$ si $R2$ pot fi reglate odata cu amplasarea fiecarui stalp, insa $R$ 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.

h2. Cerinta

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.

Cunoscand pozitiile de inceput si distanta pe care se intinde a fiecarui obiectiv, determinati raza $R$ minima ce o pot avea stalpii pentru a putea ilumina complet fiecare obiectiv, precum si numarul minim de stalpi necesari.

h2. 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.

Fisierul de intrare $light.in$ va contine pe prima linie numarul $N$ de obiective si $nr$ - numarul maxim de stalpi, iar pe urmatoarele $N$ linii cate 2 valori, {$a{~i~}$} si {$b{~i~}$}, distanta pana in punctul O al obiectivului $i$, respectiv lungimea sa.

h2. 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.

In fisierul de iesire $light.out$ se vor afisa pe o singura linie 2 valori, $Rmin$ si $nrmin$, reprezetand portiunea iluminata de fiecare stalp, precum si numarul minim de stalpi necesari.

h2. Restrictii

* 1 &le; N &le; 100.000
* 0 &le; a[i] &le; 1.000.000.000
* 1 &le; b[i] &le; 1.000.000.000
* 1 &le; nr &le; 1.000.000

* $1 &le; N &le; 100.000$
* $0 &le; a{~i~} &le; 1.000.000.000$
* $1 &le; b{~i~} &le; 1.000.000.000$
* $1 &le; nr &le; 1.000.000$

h2. Exemplu

h2. Exemple

table(example). |_. light.in |_. light.out |
| 4 4

h3. 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);

In primul caz, stalpul $1$ va ilumina portiunea {$(1, 4)$}, stalpul $2$ portiunea {$(4, 7)$}, stalpul $3$ portiunea {$(7, 10)$}, iar stalpul $4$ portiunea {$(15, 18)$}. In al doilea exemplu, primul stalp va ilumina portiunea {$(1, 5)$}, stalpul $2$ portiunea {$(6, 10)$}, iar stalpul $3$ portiunea {$(15, 19)$}.

== include(page="template/taskfooter" task_id="light") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 

2746