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.25 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Stalpi11 (clasele 11 și 12)
Pe strada principală din oraș se găsesc n stâlpi de iluminat. Pentru fiecare stâlp cunoaștem distanța d, exprimată în metri față de centrul orașului și intensitatea luminoasă a becului cd. Daca d<0, atunci stâlpul se găsește în stânga centrului, iar dacă d>0, va fi situat in dreapta. Fiecare stâlp iluminează cd metri în stânga, respectiv cd metri în dreapta. Considerăm că un segment de drum este iluminat dacă este acoperit de cel puțin un stâlp. Determinați numărul maxim de stâlpi ( nr_switchoff ) care pot fi stinși simultan astfel încât numărul segmentelor de drum iluminate să nu se schimbe. De asemenea, primarul orașului dorește să știe câți metri ( nr_black ) de drum aflați între cel mai din stânga segment iluminat și cel mai din dreapta segment iluminat sunt complet întunecați.
Date de intrare
Fișierul de intrare stalpi11.in contine pe prima linie numărul n iar pe următoarele n linii câte două numere di și cdi reprezentând distanța față de centrul orașului, respectiv intensitatea luminoasă a stâlpului i.
Date de ieșire
În fișierul de ieșire stalpi11.out vor fi scrise două 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
- În 30% din teste fiecare segment de drum va fi iluminat de cel mult un stalp
Exemplu
stalpi11.in | stalpi11.out |
---|---|
4 -2 1 8 2 5 1 7 3 |
2 5 |
Explicație
Stalpul 1 acopera segmentul -3 — -1
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 -1 — 4 nu este iluminat si are lungimea de 5m