Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | stalpi11.in, stalpi11.out | Sursă | Olimpiada pe scoala 2016 clasele 11/12 |
|---|---|---|---|
| Autor | Bogdan Marin | Adăugată de |
Bogdan Marin
•
bogdanmarin69
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 2048 KB |
| Scorul tău | N/A | Dificultate |
  1.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Stalpi11 (clasele 11 și 12)
Pe strada principala din oras se gasesc n stalpi de iluminat. Pentru fiecare stalp cunoastem distanta d metri fata de centrul orasului si intensitatea luminoasa a becului cd. Daca d<0 atunci stalpul se gaseste in stanga centrului iar daca d>0 va fi situat in dreapta. Fiecare stalp ilumineaza cd metri in stanga, respectiv cd metri in dreapta. Consideram ca un segment de drum este iluminat daca este acoperit de cel putin un stalp. Determinati numarul maxim de stalpi( nr_switchoff ) care pot fi stinsi astfel incat numarul segmentelor de drum iluminate sa nu se schimbe. Deasemenea primarul orasului doreste sa stie cati metri( nr_black ) de drum aflati intre cel mai din stanga segment iluminat si cel mai din dreapta segment iluminat sunt complet intunecate.
Date de intrare
Fișierul de intrare stalpi11.in contine pe prima linie numarul n iar pe urmatoarele n linii cate doua numere di si cdi reprezentand distanta fata de centrul orasului respectiv intensitatea luminoasa a stalpului i.
Date de ieșire
În fișierul de ieșire stalpi11.out vor fi scrise doua numere naturale:nr_switchoff si nr_black
Restricții
- 1 ≤ n ≤ 100 000
- 0 ≤ |di| ≤ 1 000 000 000
- 1 ≤ cdi ≤ 1 000 000 000
Exemplu
| stalpi11.in | stalpi11.out |
|---|---|
| 4 2 1 8 2 5 1 7 3 |
2 1 |
Explicație
Stalpul 1 acopera segmentul 1 – 3
Stalpul 2 acopera segmentul 6 – 10
Stalpul 3 acopera segmentul 4 – 6
Stalpul 4 acopera segmentul 4 – 10
Observam ca stalpii 2 si 3 pot fi stinsi fara a schimba numarul segmentelor iluminate, deasemenea segmentul 3-4 nu este iluminat si are lungimea de 1m
