// Soluzione dll'esercizio 4 del 14/6/07  


#include <stdio.h>
#include <stdlib.h>

int torriric(int i, int n, int r, int bg);
int torripd(int n);

int main(int argc,char **argv)
{
  int n; 

  if(argc==2)  {
    n = atoi(argv[1]);
    printf("Ricorsione: %d\n",torriric(0,n,0,0));
    printf("Programmazione Dinamica: %d\n",torripd(n));
  }
  return 0;
}


// ************ soluzione ricorsiva

// i = altezza attuale
// n = altezza da raggiungere
// r = totale mattoncini rossi
// bg = totale mattoncini gialli e blu
// L'idea e' di contare in quanto modi diversi la torre corrente di altezza
// i  puo' essere estesa ad una torre di altezza n legale
int torriric(int i, int n, int r, int bg)
{
  int tot=0;
  if(i==n) return 1;  // questa e' una soluzione di altezza n legale 
  if(r>bg) { // posso estendere con g o con b
    tot += 2*torriric(i+1, n, r, bg+1);
  }  
  tot += torriric(i+1, n, r+1, bg); // posso sempre estendere con un r
  return tot;
}


// soluzione basata sulla programmazione dinamica

int torripd(int n)
{
  int i,j,tot,m[n+1][n+1]; // gli indici vanno fino a n

  // in  m[i][j] metto il numero di torri distinte alte i con j mattoni 
  // rossi che soddisfano il vincolo 2*j >= i

  // vengono riempite tutte e sole le posizioni m[i][j] con
  // 1 <= i <=n   (i e' l'altezza della torre)
  // 0 <= j <=i   (j e' il numero di mattoncini rossi)
  
  m[1][0] = 0;  // nessuna torre alta 1 senza mattoni rossi
  m[1][1] = 1;  // 1 torre alta 1 con 1 mattone rosso

  for(i=2;i<=n;i++) {      
    // risolvo il caso con torri alte i
    for(j=0;j<=i;j++) {
      if(2*j<i) 
	m[i][j] = 0;  // i rossi sono meno della meta' 
      else {
        // aggiungo un rosso a una torre alta i-1 con j-1 rossi 
	m[i][j] = m[i-1][j-1]; 
	// aggiungo blu/giallo a una torre alta i-1 con j rossi
	if(j<=i-1)  
	  m[i][j] += 2*m[i-1][j]; // j<=i-1 garantisce che leggiamo da una
                                  // posizione di m precedentemente riempita
      }
    }
  }
  // calcolo e resituisco il numero totale di torri alte n legali
  tot=0;
  for(j=0;j<=n;j++)
    tot += m[n][j];
  return tot;
}