.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » domino1

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
domino1


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

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.

Cerinţă

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 domino1.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 domino1.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ă


Exemple

domino1.indomino1.outExplicaţii
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

autor: Prof. Adriana Simulescu
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
surse trimise | ajutor