Rezolvare completă PbInfo #715 Cladire4

Mircea şi Andrei sunt pasionaţi de construcţiile realizate din piese Lego. Fiecare dintre ei are un set format din N cuburi negre de latură 1 şi mai multe piese paralelipipedice de culoare albă cu care va construi o clădire de formă paralelipipedică având baza un pătrat de latură 2 şi înălţimea H.

Toate piesele de culoare albă au înălţimea 2 iar celelalte laturi egale cu 1 şi nu pot fi răsturnate în momentul în care se asamblează pentru a construi clădirea. Aceasta va conţine întotdeauna toate piesele negre din set şi atâtea piese de culoare albă cât e necesar pentru finalizarea ei.

În momentul finalizării clădirii, cei doi băieţi observă că deşi au folosit aceleaşi seturi de piese, cele două clădiri sunt diferite deoarece combinaţiile de culori alb-negru de pe faţadele (nordică, sudică, vestică sau estică) clădirilor nu arată la fel.

Cerința

Scrieţi un program care să calculeze numărul T de clădiri diferite care se pot construi cu piesele date, ştiind că două clădiri sunt identice dacă sunt îndeplinite simultan următoarele condiţii:

  • faţada dinspre nord a uneia este identică cu faţada dinspre nord a celeilalte;
  • faţada dinspre est a uneia este identică cu faţada dinspre est a celeilalte;
  • faţada dinspre sud a uneia este identică cu faţada dinspre sud a celeilalte;
  • faţada dinspre vest a uneia este identică cu faţada dinspre vest a celeilalte.

Programul va afişa restul împărţirii numărului T la 666013.

Date de intrare

Fișierul de intrare cladire4.in conține pe prima linie două numere naturale N şi H (în această ordine), separate printr-un spaţiu şi având semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire cladire4.out va conține pe prima linie un singur număr natural ce reprezintă restul împărţirii numărului T la 666013.

Restricții și precizări

  • N, H sunt numere naturale şi N este număr par;
  • 2 ≤ N ≤ 4H şi 1 ≤ H ≤ 1000;
  • există atâtea piese albe câte sunt necesare;
  • o piesă de culoare albă se va aşeza întotdeauna cu baza de latură 1, peste o altă piesă a clădirii sau la baza acesteia;
  • cu piesele date se poate construi cel puţin o clădire;
  • pentru 30% din teste H ≤ 25.

Exemplu

cladire4.in

2 2

cladire4.out

4

Explicație


Exemplu

cladire4.in

4 3

cladire4.out

16

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

// Cristina Iordaiche 
// programare dinamica 100puncte
#include<fstream>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))

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

const long MOD=666013;

int n,h,h4,lim;
long a[3][4001];
int i,i1,i2,j,k,tmp;

int main()
{
      fin>>n>>h;
      fin.close();
     
      if(h==1)
      {
            fout<<1<<'\n';
            fout.close();
            return 0;
      }
     
      h4=4*h;
     
      a[1][1]=1;
      a[2][0]=1;
      a[2][2]=1;
     
      i2=1; i1=2; i=0;
     
      for(k=3;k<=h4;k++)
      {
            lim=min(n,k);
           
            if((k-1)%h)
            {
                  a[i][0]=a[i2][0];
     
                  for(j=1;j<=lim;j++)
                  {
                        a[i][j]=(a[i1][j-1]+a[i2][j])%MOD;
                  }
            }
            else
            {
                  a[i][0]=0;
                 
                  for(j=1;j<=lim;j++)
                  {
                        a[i][j]=a[i1][j-1];
                  }
            }
           
            tmp=i; i=i2; i2=i1; i1=tmp;
      }
     
      fout<<(a[i1][n])<<'\n';
     
      fout.close();
      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 #715 Cladire4

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