Fișierul intrare/ieșire | piramide.in, piramide.out | Sursă | OJI 2014 clasa a 5-a |
---|---|---|---|
Autor | Carmen Mincă | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Piramide (clasa a 5-a)
Fascinat de Egiptul Antic, Rareș vrea să construiască cât mai multe piramide din cartonașe pătratice identice. El are la dispoziție N cartonașe numerotate de la 1 la N, albe sau gri, așezate în ordinea strict crescătoare a numerelor.
- Prima piramidă o va construi folosind primele trei cartonașe. Baza piramidei va fi formată din cartonașele 1 și 2 așezate alăturat, peste care va așeza cartonașul 3 (vârful piramidei).
- A doua piramidă va avea baza formată din cartonașele 4,5 și 6 așezate alăturat, deasupra cărora se vor așeza cartonașele 7 și 8, alăturate, peste care se va așeza cartonașul 9 (vârful piramidei).
- Mai departe, va construi în ordine piramidele complete cu bazele formate din 4 cartonașe (cu numerele de la 10 la 13), respectiv 5 cartonașe (cu numerele de la 20 la 24), 6 cartonașe (cu numerele de la 35 la 40) etc., cât timp va putea construi o piramidă completă. De exemplu, dacă Rareș are N=75 cartonașe atunci el va construi piramidele complete 1,2,3,4 și 5 din imaginile următoare. Din cele 75 de cartonașe el va folosi doar primele 55 de cartonașe, deoarece ultimele 20 cartonașe nu sunt suficiente pentru a construi piramida 6, cu baza formată din 7 cartonașe.
Cerință
Scrieți un program care să citească numerele naturale N (reprezentând numărul de cartonașe), X (reprezentând numărul unui cartonaș), K (reprezentând numărul de cartonașe albe), numerele celor K cartonașe albe c1,c2,...,cK și care să determine: a) numărul P al piramidei complete ce conține cartonașul numerotat cu X; b) numărul M maxim de piramide complete construite de Rareș; c) numărul C de cartonașe nefolosite; d) numărul A al primei piramide complete care conține cele mai multe cartonașe albe.
Date de intrare
Fișierul de intrare piramide.in conține pe prima linie cele trei numere N, X și K, separate prin câte un spațiu, cu semnificația din enunț. A doua linie a fișierului conține, în ordine, cele K numere c1,c2,...,cK, separate prin câte un spațiu, reprezentând numerele celor K cartonașe albe din cele N.
Date de ieșire
Fișierul de ieșire piramide.out va conține pe prima linie numărul P sau valoarea 0 (zero) dacă niciuna dintre piramidele complete construite nu conține cartonașul cu numărul X. A doua linie a fișierului va conține numărul M. Cea de-a treia linie va conține numărul C. Cea de-a patra linie va conține numărul A sau valoarea 0 (zero) dacă nicio piramidă completă nu conține cel puțin un cartonaș alb.
Restricții
- N, X, K, c1,c2,...,cK, P, M, A sunt numere naturale nenule.
- 3 ≤ N ≤ 100000; 1 ≤ X ≤ N; 1 ≤ K ≤ N; 1 ≤ c1 < c2 <...< cK ≤ N
- O piramidă completă cu baza formată din b cartonașe se construiește prin așezarea cartonașelor necesare pe b rânduri: b cartonașe pe primul rând (al bazei), apoi b-1 cartonașe pe rândul al doilea, b-2 pe rândul al treilea,..., două cartonașe pe rândul b-1 și un cartonaș (vârful piramidei) pe rândul b.
- Pentru rezolvarea cerinței a) se acordă 20% din punctaj, pentru cerința b) 20% din punctaj, pentru cerința c) 20% din punctaj și pentru cerința d) 40% din punctaj.
Exemplu
piramide.in | piramide.out | Explicații |
---|---|---|
75 15 23 5 9 11 18 20 21 25 27 28 30 35 37 45 46 51 55 60 65 68 69 70 71 72 |
3 5 20 4 |
Piramida 3 (P=3) construită conține cartonașul cu numărul X=15. Rareș poate construi doar M=5 piramide complete, rămânând nefolosite 20 cartonașe (C=20) insuficiente pentru construirea piramidei 6. Numărul maxim de cartonașe albe dintr-o piramidă completă este egal cu 6. Piramidele 4 și 5 conțin fiecare un număr maxim de cartonașe albe (6), prima dintre acestea fiind piramida 4 (A=4). Ultimele 7 cartonașe albe (cu numerele: 60,65,68,69,70,71,72) nu sunt folosite în construirea piramidelor complete. |