Fişierul intrare/ieşire:pitici3.in, pitici3.outSursăLot Iasi 2008, Baraj 5
AutorEmanuela CerchezAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pitici3

N pitici (numerotaţi de la 1 la N) au căzut într-o groapă adâncă de D cm. Fiecare pitic îşi cunoaşte înălţimea umerilor (adică distanţa de la pământ la umerii săi), precum şi lungimea braţelor. Prin urmare, dacă piticul i ( 1 ≤ i ≤ N ) are înălţimea umerilor Hi cm şi lungimea braţelor Li cm, atunci când el va sta în picioare cu braţele în sus va atinge înălţimea Hi + Li cm.

Piticii se pot urca unii pe umerii celorlalţi formând astfel un singur turn. Dacă piticul i stă cu mânile întinse şi este urcat pe umerii piticului jk, care stă pe umerii lui jk-1, ... care stă pe umerii lui j1 atunci el va atinge înălţimea Hj1 + Hj2 + … + Hjk + Hi + Li.

Dacă un pitic atinge marginea gropii (adică Hj1 + Hj2 + … + Hjk + Hi + Li ≥ D), el poate ieşi din groapă.

Cerinţă

Să se determine numărul maxim de pitici care pot ieşi din groapă.

Date de intrare

Fişierul de intrare pitici3.in conţine pe prima linie numărul natural N reprezentând numărul de pitici. Pe următoarele N linii sunt descrişi piticii. Mai exact, pe linia i+1 se află două numere naturale separate prin spaţiu Hi şi Li reprezentând înălţimea umerilor şi respectiv lungimea braţelor piticului i ( 1 ≤ i ≤ N ). Pe ultima linie este scris un număr natural D reprezentând adâncimea gropii.

Date de ieşire

Fişierul de ieşire pitici3.out va conţine o singură linie pe care va fi scris numărul natural X reprezentând numărul maxim de pitici care pot ieşi din groapă.

Restricţii

  • 1 ≤ N ≤ 2000
  • 1 ≤ Hi ≤ 105 (1 ≤ i ≤ N)
  • 1 ≤ Li ≤ 105 (1 ≤ i ≤ N)
  • 1 ≤ D ≤ 105
  • Piticii care ies nu mai intră înapoi.
  • Pentru 70% din teste N ≤ 100 ; D, Hi, Li ≤ 1000.

Exemplu

pitici3.inpitici3.out
7
2 4
3 2
4 1
7 5
2 1
6 4
6 1
30
3

Explicaţie

De exemplu, pot ieşi piticii 1, 5 si 6.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content