Fișierul intrare/ieșire piramide.in, piramide.out Sursă OJI 2014 clasa a 5-a
Autor Carmen Mincă Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.5 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii