Using DP
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int f[35]; int g[35]; int main() { for(int i=0;i<35;i++) f[i]=g[i]=0; f[0]=1; f[1]=0; g[0]=0; g[1]=1;//one missing cornered rect of size 3x1 for(int i=2;i<35;i++) { f[i]=f[i-2]+2*g[i-1];//if last column are 3 of (2x1) OR one vertical 2x1(and removing that will leave one missing cornered ractngle of 2 ways) g[i]=f[i-1]+g[i-2];//one missing cornered rectangle can be 1.last one vertical 2x1 and 2. 2 horizontal 2x1 if we remove them wil form another missing cornered rectangle } int n; while(scanf("%d",&n) && n!=-1) { printf("%d\n",f[n]); } return 0; } |
Another way of adhoc suggested in a blog.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int arr[35]; //lets assume if last column are all horizontal tiles of 3 *(2x1), so remove that and this 3*(2x1) can be // tiled 3 ways ,so total ways for n length is ways[n-2]*3 //if n>=4 then for every term it can be shifted upside down adds two more ways // so for n>=4 int main() { for(int i=0;i<35;i++) arr[i]=0; arr[0]=1; for(int i=2;i<35;i+=2) { arr[i]+=3*arr[i-2]; for(int j=4;j<=i;j+=2) { arr[i] += 2*arr[i-j]; } } int n; while(scanf("%d",&n) && n!=-1) { printf("%d\n",arr[n]); } return 0; } |