Inverseaza reviziile

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

Diferente intre #1 si #2

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.

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

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