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țe

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 c₁, c₂, …, c_K ș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 c₁, c₂,…, c_K, 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 și precizări

N, X, K, c₁, c₂,…, c_K, P, M, A sunt numere naturale nenule.
3 ≤ N ≤ 100000; 1 ≤ X ≤ N; 1 ≤ K ≤ N; 1 ≤ c₁ < c₂ <...< c_K ≤ 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

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

piramide.out

Explicație

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Piramide:

//sursa oficiala - prof. Carmen Minca - C.N.I.T.Vianu- Bucuresti

#include <fstream>
using namespace std;
/*a) numarul P al piramidei ce conține cartonasul numerotat cu X;
  b) numarul M maxim de piramide construite de Gigel;
  c) numarul C de cartonașe nefolosite;
  d) numarul A al primei piramide care contine cele mai multe cartonașe albe.
*/
int n, x, k;
ifstream f("piramide.in");
ofstream g("piramide.out");

int main()
{
    int p=0, a=0, m=0, c=0,i,ca,b=1,cfol=0,cp,nra, maxnra=0;
    f>>n>>x>>k;
    i=1;
    f>>ca;
    do  //caut piramida ce contine cartonasul alb cu numarul ca
        {  b++;//nr cartonase din baza piramida curenta
           nra=0;//caut in piramida curenta cartonasele albe
           cp=b*(b+1)/2; //nr cartonase din care e formata piramida curenta
           if(cp+cfol<=n)  //daca am cele cp cartoane atunci pot construi piramida
             {  m++; //numar piramida construita
                if(cfol<x && x<=cp+cfol) p=m; //verif daca contine cartonasul x
                cfol+=cp;
                while(ca<=cfol && i<=k)
                    { nra++;f>>ca;i++;} //numar cartonasele albe din piramida
                if(nra>maxnra)
                    { a=m; maxnra=nra; }
             }
             else break;
         } while (cfol<n);
    c=n-cfol;
    g<<p<<endl<<m<<endl<<c<<endl<<a<<endl;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1044 Piramide

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1044 Piramide de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1044 Piramide