Ionuţ a învăţat la şcoală să lucreze cu numere mari. El are la dispoziţie un şir de N numere naturale nenule. Din fiecare număr el şterge exact trei cifre, fără să schimbe ordinea cifrelor rămase, astfel încât să obţină cel mai mic număr natural nenul posibil. De exemplu, din numărul 20731049 se obţine numărul 20049, iar din numărul 13004 se obţine numărul 10. Înlocuind fiecare număr citit cu numărul obţinut prin operaţia de mai sus, Ionuţ obţine un nou şir şi scrie termenii acestuia pe feţele unor cuburi astfel: primele şase numere din şir le scrie pe primul cub şi îl notează pe acesta cu 1, următoarele şase numere din şir le scrie pe un alt cub pe care îl notează cu 2 ş.a.m.d.

Aceste cuburi au fost distribuite în piramide după modelul din figura. Piramidele au fost numerotate cu numere naturale consecutive. Piramida cu numărul de ordine 1 este formată numai din cubul cu numărul de ordine 1 şi are un singur nivel, piramida cu numărul de ordine 2 are pe primul nivel cuburile 2, 3 şi 4 iar pe ultimul nivel cubul 5 ş.a.m.d.

Două niveluri alăturate în cadrul unei piramide diferă prin exact două cuburi. Primul nivel al unei piramide conţine cu două cuburi mai mult decât primul nivel al piramidei precedente. Piramida se consideră completă dacă pe ultimul nivel are un singur cub.

Cerința

Scrieţi un program care citeşte numerele naturale nenule N şi K, apoi cele N numere naturale ce fac parte din şirul iniţial, şi determină:
a) Numărul de piramide complete construite de Ionuţ.
b) Numerele scrise pe cuburile din primele K piramide.

Date de intrare

Fişierul cuburi.in are două linii: prima linie conţine două numere naturale, N şi K, iar a doua linie conţine N numere naturale. Pe fiecare linie a fişierului numerele sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul cuburi.out are două linii: prima linie conţine numărul de piramide complete care au fost construite, iar a doua linie conţine toate numerele scrise pe cuburile ce formează primele K piramide. Numerele sunt scrise separate prin câte un spaţiu, în ordinea apariţiei lor în şirul nou obţinut.

Restricții și precizări

6 ≤ N ≤ 100000
Se garantează că se pot construi cel puţin K piramide complete.
Cele N numere naturale de pe a doua linie a fişierului de intrare au minimum 4 cifre şi maximum 9 cifre.

Exemplu

cuburi.in

31 2
18250 9280 18250 953805 20800 6040065 24208 4405 8794 1720 98886 96400 45544 8560056 36055 60400 80200 11560 36475 26992 68320 69400 20296 72640 34048 57700 66520 47440 91232 26080 90280

cuburi.out

2
10 2 10 305 20 4005 20 4 4 1 86 40 44 5005 30 40 20 10 34 22 20 40 20 20 30 50 20 40 12 20

Explicație

Primele 6 numere se găsesc pe cubul ce formează prima piramidă, următoarele 24 de numere sunt scrise, în această ordine, pe feţele cuburilor ce alcătuiesc a doua piramidă.

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 Cuburi3:

#include <stdio.h>
#include <math.h>
//using namespace std;
//ifstream f("cuburi.in");
//ofstream g("cuburi.out");

int w[100001];
int nrmin(int x,int nrc)
{
    int v[10],i,Min,imin,in,sf;
    for(i=nrc;i>=1;i--){v[i]=x%10;x=x/10;}
    Min=v[1];imin=1;
    for(i=1;i<=4;i++)
        if(v[i]<Min && v[i]!=0) {Min=v[i];imin=i;}
    int nr=Min;in=imin+1;sf=5;
    while(sf<=nrc)
    {
        Min=v[in];imin=in;
        for(i=in;i<=sf;i++)
            if(v[i]<Min){Min=v[i];imin=i;}
        nr=nr*10+Min;
        in=imin+1;sf++;         
    }       
    return nr;  
}


int main()
{
    freopen("cuburi.in","r",stdin);
    freopen("cuburi.out","w",stdout);
    int x,nrc,n,nrpir=0,i,k,j=1,nr=0,s=0;
    scanf("%d %d",&n, &k);
//  f>>n>>k;
    for(i=1;i<=k;i++)
    nr=nr+i*i*6;
    for(i=1;i<=n;i++)
    {
//  f>>x;
    scanf("%d",&x);
    nrc=(int)log10(x)+1;
    if(i%6==0 && (sqrt(i/6)==(int)sqrt(i/6))) {s=s+i;if(s<=n) nrpir++;}
    if(i<=nr) w[j++]=nrmin(x,nrc);
    }
    
    printf("%d\n",nrpir);
//  g<<nrpir<<'\n';
    for(i=1;i<j;i++)
        printf("%d ",w[i]);
//      g<<w[i]<<' ';
//  g<<'\n';
    printf("\n");

    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 #1708 Cuburi3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1708 Cuburi3 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 #1708 Cuburi3