fbpx

Problema #1044 – Piramide – Rezolvari PBInfo

de Mihai-Alexandru

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 c1, c2, …, cK și care să determine:

a) numărul P al piramidei complete ce conține cartonașul numerotat cu X;

Exemplu

piramide.in

75 15 235 9 11 18 20 21 25 27 28 30 35 37 45 46 51 55 60 65 68 69 70 71 72

piramide.out

35204

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.

#include <bits/stdc++.h>

using namespace std;
int a[100001], n;

ifstream fin("piramide.in");
ofstream fout("piramide.out");

int main()
{
    int pir = 0, nefolosite, x, c, cate, maxim = 0, nrp = 0;
    fin >> n >> x;
    a[1] = 3;
    int    ind = 1;
    while(a[ind] < n)
    {
        a[++ind] = a[ind - 1] + (ind + 1) * (ind + 2) / 2;
        if(x <= a[ind]  && x > a[ind - 1]) pir = ind;
    }
    if(a[ind] > n ) ind = ind - 1;
    if(pir > ind) pir = 0;
    nefolosite = n - a[ind]; ///numar total de cartonase - numarul din ultima completa

    fout << pir << "\n" << ind << "\n" << nefolosite << " \n";
    int t = 1, nrc = 0, cart;
    fin >> c;
    fin >> cart;
       while( a[t] < cart) ++t;
    for(int i = 2; i <= c; ++i)
    {
        if(cart == a[t]) nrc = 1;
        else
        {
           if(cart < a[t] && t <= ind)nrc++;
           else
           {
               t++;
               nrc = 0;
           }
        }
        if(nrc > maxim)
        {
            maxim = nrc;
            nrp = t;
        }
        fin >> cart;
    }

     fout << nrp ;

    return 0;
}
Comentarii

S-ar putea sa iti placa