Andra este o fetiță pasionată de desen. Pentru a-și îmbunătăți performanțele școlare la geometrie, Andra îmbină pasiunea pentru desen cu rezolvarea problemelor de geometrie. Astfel, pe o foaie de matematică împărțită în pătrățele dispuse pe \(2^N \) linii şi \(2^N \) coloane, Andra desenează în centru o figură de forma unui pătrat de latură \(2^{N-1} \) (figura 1) . Pentru fiecare colț al figurii, Andra desenează alte 4 noi figuri cu latura egală cu jumătate din latura figurii inițiale (Figura 2). Repetă procedeul de desenare pentru fiecare nouă figură obținută, până când ajunge la marginea foii de hârtie, fără a depăși marginile acesteia. Fiecare pătrățel care face parte dintr-o figură desenată este colorat, pentru a se distinge pe foaia de hârtie. Fiecare figură desenată este un pătrat cu laturile paralele cu marginile foii de hârtie.
Cerința
Scrieţi un program care citește numărul N , corespunzător dimensiunii de \(2^N\) x \(2^N \) a foii de desen şi determină:
1) Numărul de figuri de latură minimă desenate;
2) Numărul total de pătrățele colorate cel puțin o dată de pe foaia de hârtie.
Date de intrare
Fişierul de intrare fractal.in conţine pe prima linie numărul natural C reprezentând cerința din problemă care
trebuie rezolvată (1 sau 2) și pe a doua linie, un număr natural N cu semnificația de mai sus.
Date de ieșire
Dacă valoarea lui C este 1, fişierul de ieşire fractal.out va conţine un număr natural care reprezintă numărul
de figuri de latură minimă. Dacă valoarea lui C este 2, fişierul de ieşire fractal.out va conţine un număr
natural care reprezintă numărul total de pătrățele colorate cel puțin o dată de pe foaia de hârtie.
Restricții și precizări
1 < N ≤ 10000- Pentru 30% dintre teste
N≤30 - Pentru rezolvarea corectă a cerinţei 1 se obțin 30 de puncte, iar pentru rezolvarea corectă a cerinţei 2 se obțin
70 de puncte.
Exemplu 1:
fractal.in
1 4
fractal.out
16
Explicație
Suprafața de desen are 16 linii și 16 coloane (figura 3). Pornind de la figura inițială se vor desena mai întâi 4 figuri, apoi 16 figuri.
Exemplu 2:
fractal.in
1 5
fractal.out
64
Explicație
Suprafața de desen are 32 linii și 32 coloane (figura 4). Pornind de la figura inițială se vor desena mai întâi 4 figuri, apoi 16 figuri, respectiv 64 figuri de latură minimă.
Exemplu 3:
fractal.in
2 4
fractal.out
148
Explicație
Suprafața desenată este cea din figura 3. Numărul de pătrățele colorate cel puțin o dată este de 148 din totalul de 256 de pătrățele.
fractal.in
2 5
fractal.out
700
Explicație
Suprafața desenată este cea din figura 4. Numărul de pătrățele colorate cel puțin o dată este de 700 din totalul de 1024 de pătrățele.
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 fractal:
#include <fstream>
using namespace std;
ifstream fin("fractal.in");
ofstream fout("fractal.out");
unsigned N,C,i,j,ct,a[100001],b[100001],p;
int main()
{
fin>>C>>N;
///cerinta 1
if(C==1)
{
///calculam 4 la puterea N-2
a[0]=a[1]=1;
for(i=1;i<=N-2;i++)
{
for(j=1,ct=0;j<=a[0];j++)
{ a[j]=a[j]*4+ct;ct=a[j]/10; a[j]=a[j]%10;}
while(ct){a[0]++;a[a[0]]=ct%10;ct/=10;}
}
for(j=a[0];j>=1;j--)
fout<<a[j];
fout<<'\n';
return 0;
}
///cerinta 2
///calculam 4 la N in vect a
a[0]=1;a[1]=1;
for(i=1;i<=N;i++)
{
for(j=1,ct=0;j<=a[0];j++)
{ a[j]=a[j]*4+ct;ct=a[j]/10; a[j]=a[j]%10;}
while(ct){a[0]++;a[a[0]]=ct%10;ct/=10;}
}
///calculam 4*(3^(N-1)) in vect b
b[0]=1;b[1]=4;
for(i=1;i<=N-1;i++)
{
for(j=1,ct=0;j<=b[0];j++)
{ b[j]=b[j]*3+ct;ct=b[j]/10; b[j]=b[j]%10;}
while(ct){b[0]++;b[b[0]]=ct%10;ct/=10;}
}
///in final calculez (4^N)-4*(3^(N-1))
for(i=1,ct=0;i<=a[0];i++)
{
if(a[i]>=b[i]+ct){a[i]=a[i]-ct-b[i];ct=0;}
else
{a[i]=a[i]+10-ct-b[i];ct=1;}
}
while(a[a[0]]==0)a[0]--;///nu e cazul, dar...
///afisam rezultatul final
for(j=a[0];j>=1;j--)
fout<<a[j];
fout<<'\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 
.
Rezolvarea problemei #2472 fractal
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2472 fractal 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!