Fișierul intrare/ieșire elfi.in, elfi.out Sursă OJI 2006 clasa a 8-a
Autor Rodica Pintea Adăugată de avatar Emplopi Stefan Nitu Emplopi
Timp de execuție pe test 0.2 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Elfi (clasa a 8-a)

Marele vrăjitor Prospero are o grădină minunată îngrijită de o sumedenie de spiriduși care n-au altă sarcină decât să zboare la orele dimineții de-a lungul aleilor și să stropească plantele din vasele ornamentale de piatră aflate pe margine. Există un havuz chiar la capătul grădinii și o alee principală ce pornește de la havuz și duce până la intrare. Din aleea principală se desprind alei secundare ce formează ronduri alungite revenind, în același loc, la aleea principală.
Se știe că există n spiriduși, numerotați de la 1 la n, fiecare pentru câte una dintre aleile secundare. Toți pornesc de la havuz la ora 5:00:00 dimineața cu câte un vas cu apă pregătit de cu seară, străbat aleea principală până la rondul lor, apoi parcurg aleea rondului propriu, revin în aleea principală, se întorc la havuz pentru a se alimenta cu apă și o iau de la capăt la fel, până la ora 9:00:00 când se retrag la umbră pentru somn. Se știe că toți spiridușii zboară fără încetare, cu aceeași viteză, pe toată durata celor exact 4 ore. Se cunosc, pentru fiecare spiriduș, numărul de secunde necesare pentru a ajunge de la havuz la rondul propriu și numărul de secunde necesare pentru a parcurge în întregime rondul propriu. Orice spiriduș care ajunge la havuz își umple vasul în exact o secundă, de la un robinet aflat pe marginea havuzului. De exemplu, dacă spiridușul care se ocupă de rondul 5 din figură are nevoie de 2 secunde pentru a ajunge la rondul său și de 15 secunde pentru a parcurge rondul 5, atunci va reveni la havuz pentru a-și umple vasul la orele 5:00:19 (2+15+2), își umple vasul și pornește iar la ora 5:00:20, revine iar la 5:00:39 și pleacă iar la ora 5:00:40 etc.
Doi spiriduși nu își pot umple vasul în același moment de la același robinet.

Date de intrare

Din fișierul de intrare elfi.in se citesc:

  • n numărul de spiriduși, de pe primul rând;
  • n perechi de forma ci pi reprezentând numărul de secunde de la havuz la rondul propriu și respectiv numărul de secunde necesar pentru parcurgerea rondului propriu, de pe următoarele n linii ale fișierului.

Date de ieșire

În fișierul de ieșire elfi.out se scrie o singura linie cu un singur număr reprezentând numărul minim de robinete necesare.

Restricții

  • 2 ≤ n ≤ 5 000
  • 1 ≤ ci ≤ 100
  • 1 ≤ pi ≤ 100

Exemplu

elfi.in elfi.out Explicație
5
7 4
7 8
4 5
7 6
2 15
4
Primul, al treilea, al patrulea și al cincilea spiriduș se întâlnesc simultan la havuz la
ora 7:12:59 și-și umplu vasele până la ora 7:13:00.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii