Fişierul intrare/ieşire:domino2.in, domino2.outSursăONI 2010 clasa a 5-a
AutorAdriana SimulescuAdăugată dedumitriu_razvanRazvan Dumitriu dumitriu_razvan
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Domino2

Ionel are n piese de domino de diverse înălţimi. În joacă, el aşează piesele vertical într-un şir (pe o riglă gradată), la distanţe nu neapărat egale una faţă de alta. Ionel atinge prima piesă, aceasta cade şi poate antrena în cădere după ea şi alte piese din şir. Dacă mai rămân piese în picioare, el merge la prima piesă care nu a căzut şi o atinge. Aceasta cade şi poate antrena în cădere după ea şi alte piese. Continuă procedeul până când nu mai rămâne nicio piesă în picioare.

Cerinta

Scrieţi un program care să citească numărul natural n de piese, poziţia pe riglă şi înălţimea fiecărei piese, în această ordine, şi care să determine numărul minim necesar de atingeri ale pieselor astfel încât să cadă toate piesele de domino precum şi numărul maxim de piese răsturnate la o singură atingere.

Date de intrare

Fişierul de intrare domino2.in conţine pe prima linie numărul natural n. Pe fiecare dintre următoarele n linii se află câte două numere naturale p şi h, separate printr-un spaţiu, p reprezentând poziţia piesei pe riglă şi h înălţimea piesei de domino, în această ordine.

Date de ieşire

Fişierul de ieşire domino2.out va conţine o singură linie pe care sunt scrise două numere naturale a şi b , în această ordine, separate printr-un spaţiu, a reprezentând numărul minim necesar de atingeri ale pieselor, iar b numărul maxim de piese ce sunt răsturnate la o singură atingere a unei piese.

Restricţii

  • Numerele n, p şi h sunt numere naturale nenule
  • 1<=n<=1000
  • 1<=p<=5000
  • 1<=h<=5000
  • O piesă de domino aflată pe pozitia p de înălţime h răstoarnă piese până la poziţia p+h inclusiv.
  • În fişierul de intrare datele sunt în ordinea crescătoare a poziţiei pieselor de domino.
  • Pe o poziţie de pe riglă se poate afla o singură piesă de domino.
  • Ionel începe întotdeauna cu piesa aşezată la poziţia cea mai mică

Exemplu

domino2.indomino2.outExplicatii
5
10 10
14 10
27 2
28 10
37 5
2 3
La atingerea primei piese vor cădea primele două piese;
Atingea piesei de pe poziţia 27 răstoarnă piesa de pe poziţia 28
iar aceasta o răstoarnă şi pe ultima
Numărul de atingeri este 2 iar numărul maxim
de piese doborâte la o atingere este 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici