Fişierul intrare/ieşire:piramide.in, piramide.outSursăOJI 2014 clasa a 5-a
AutorCarmen MincaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inpiramide.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici