== include(page="template/taskheader" task_id="domino2") ==
Poveste și cerință...
_Notă: această problemă are afișarea diferită față de original: cele două numere vor fi afișate pe linii diferite._
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.
!problema/domino2?x.jpg!
h2. 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.
h2. Date de intrare
Fișierul de intrare $domino2.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $domino2.out$ ...
Fișierul de ieșire $domino2.out$ va conține două linii. Pe prima linie veți scrie *a* reprezentând numărul minim necesar de atingeri ale pieselor, iar pe a doua linie veți scrie *b*, numărul maxim de piese ce sunt răsturnate la o singură atingere a unei piese.
h2. 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ă.
* Se acordă 50% din punctaj pentru rezolvarea corectă a fiecărei cerințe.
h2. Exemplu
table(example).
|_. domino2.in |_. domino2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. domino2.in |_. domino2.out |_. Explicatii |
|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
|
== include(page="template/taskfooter" task_id="domino2") ==
