Mihai a găsit pe facebook o poză cu triunghiuri echilaterale aşezate în formă de piramidă, ca în figura de mai jos. El observă că piramida este compusă din mai multe benzi. Prima bandă conţine un triunghi echilateral, a doua bandă conţine 3 triunghiuri echilaterale, dintre care cel din mijloc este cu vârful în jos, a treia bandă conţine 5 triunghiuri echilaterale şi aşa mai departe.
El constată că fiecare triunghi de cea mai mică dimensiune poate fi divizat în mai multe triunghiuri și mai mici prin procedeul de împărțire a unui triunghi. Prin acesta se înțelege unirea mijloacelor laturilor triunghiului, două câte două, printr-un segment, obținându-se astfel 4 triunghiuri mai mici ce compun triunghiul respectiv, ca în figura următoare.
Mihai a analizat acest proces și a stabilit că dacă un triunghi este supus procedeului de împărțire, atunci toate triunghiurile din piramidă de dimensiunea lui vor trece prin acest procedeu. Astfel, el își pune următoarea întrebare: având N piramide, fiecare având un anumit număr de benzi, câte triunghiuri de cea mai mică dimensiune și câte perechi de drepte paralele are fiecare piramidă, după ce s-a executat procedeul de împărțire de M ori pe toate piramidele?
În prima figură o pereche de drepte paralele este formată din dreapta situată între benzile 2-3 și o dreaptă situată între benzile 3-4.
Cerința
Cunoscând N, M și câte benzi are fiecare piramidă, se cere să se afișeze:
a) câte triunghiuri de cea mai mică dimensiune are fiecare piramidă, după executarea procedeului de împărțire de M ori;
Mihai a găsit pe facebook o poză cu triunghiuri echilaterale aşezate în formă de piramidă, ca în figura de mai jos. El observă că piramida este compusă din mai multe benzi. Prima bandă conţine un triunghi echilateral, a doua bandă conţine 3 triunghiuri echilaterale, dintre care cel din mijloc este cu vârful în jos, a treia bandă conţine 5 triunghiuri echilaterale şi aşa mai departe.
El constată că fiecare triunghi de cea mai mică dimensiune poate fi divizat în mai multe triunghiuri și mai mici prin procedeul de împărțire a unui triunghi. Prin acesta se înțelege unirea mijloacelor laturilor triunghiului, două câte două, printr-un segment, obținându-se astfel 4 triunghiuri mai mici ce compun triunghiul respectiv, ca în figura următoare.
Mihai a analizat acest proces și a stabilit că dacă un triunghi este supus procedeului de împărțire, atunci toate triunghiurile din piramidă de dimensiunea lui vor trece prin acest procedeu. Astfel, el își pune următoarea întrebare: având N piramide, fiecare având un anumit număr de benzi, câte triunghiuri de cea mai mică dimensiune și câte perechi de drepte paralele are fiecare piramidă, după ce s-a executat procedeul de împărțire de M ori pe toate piramidele?
În prima figură o pereche de drepte paralele este formată din dreapta situată între benzile 2-3 și o dreaptă situată între benzile 3-4.
Cerința
Cunoscând N, M și câte benzi are fiecare piramidă, se cere să se afișeze:
a) câte triunghiuri de cea mai mică dimensiune are fiecare piramidă, după executarea procedeului de împărțire de M ori;
b) câte perechi de drepte paralele are fiecare piramidă, după executarea procedeului de împărțire de M ori.
Date de intrare
Fişierul de intrare tripar.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Următoarea linie va conține numerele N și M separate printr-un un spațiu. Pe următoarea linie se vor afla N numere naturale, al i-lea număr reprezintă numărul de benzi pe care, inițial, piramida i le are.
Date de ieșire
Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință. În acest caz, fişierul de ieşire tripar.out va conține N linii; pe linia i se va scrie un număr natural reprezentând, numărul de triunghiuri de cea mai mică dimensiune pe care piramida i le conține după executarea procedeului de M ori.
Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință. În acest caz, fişierul de ieşire tripar.out va conține N linii; pe linia i se va scrie un număr natural reprezentând, numărul de perechi de drepte paralele pe care piramida i le conține după executarea procedeului de M ori.
Restricții și precizări
1 ≤ N ≤ 50 0000 ≤ M ≤ 101 ≤ numărul inițial de benzi al fiecărei piramide ≤ 50- Pentru rezolvarea corectă a primei cerinţe se acordă 40 de puncte, iar pentru cerința a doua se acordă 60 de puncte.
Exemplul 1:
tripar.in
1 3 0 1 2 3
tripar.out
1 4 9
Explicație
p = 1
Deoarece nu are loc niciun procedeu de împărțire se calculează direct numărul de triunghiuri de cea mai mică dimensiune pe care fiecare piramidă îl are.
Atenție! Pentru acest test se rezolvă doar cerința a).
Exemplul 2:
tripar.in
2 3 0 1 2 3
tripar.out
0 3 9
Explicație
p = 2
Deoarece nu are loc niciun procedeu de împărțire se calculează direct numărul de perechi de drepte paralele pe care fiecare piramidă îl are.
Atenție! Pentru acest test se rezolvă doar cerința b).
Exemplul 3:
tripar.in
1 2 1 1 2
tripar.out
4 16
Explicație
p = 1
Procedeul de împărțire se realizează o singură dată, iar dupa aceea prima piramidă va avea două benzi și cea de-a doua va avea 4 benzi. Se poate calcula acum numărul de triunghiuri de cea mai mică dimensiune pe care fiecare piramidă îl are.
Atenție! Pentru acest test se rezolvă doar cerința a).
Exemplul 4:
tripar.in
2 2 1 1 2
tripar.out
3 18
Explicație
p = 2
Procedeul de împărțire se realizează o singură dată, iar dupa aceea prima piramidă va avea două benzi și cea de-a doua va avea 4 benzi. Se poate calcula acum numărul de perechi de drepte paralele pe care fiecare piramidă îl are.
Atenție! Pentru acest test se rezolvă doar cerința b).
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("tripar.in");
ofstream fout ("tripar.out");
long long cer, n, m, p[50005], putere, rez;
int main()
{
fin >> cer >> n >> m;
for(int i=1; i<=n; i++)fin >> p[i];
if (cer == 1)for(int i=1; i<=n; i++)
{
putere = pow(4, m);
p[i]*=p[i];
fout << p[i]*putere << '\n';
}
else for(int i=1; i<=n; i++)
{
putere=pow(2, m);
rez = p[i]*putere;
rez = rez*(rez - 1);
fout << 3*rez/2 << '\n';
}
return 0;
}
