Fişierul intrare/ieşire:stalpi11.in, stalpi11.outSursăOlimpiada pe scoala 2016 clasele 11/12
AutorBogdan MarinAdăugată debogdanmarin69Bogdan Marin bogdanmarin69
Timp execuţie pe test0.25 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Stalpi11 (clasele 11/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.instalpi11.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici