1020 Anniversary Cake
問題概要
s×sの正方形のケーキがある。これを余りが出ないように、n個に切り分けたい。
n個はそれぞれ一辺がa[i]の正方形でなければならない。
これが可能かどうか調べよ。
n≦16, a[i]≦10を満たす。 a[i]は正整数である。
解法
kusano_progさんの解法を参考にさせていただいた。
正方形のケーキをsxsの配列でもち、切った部分を0にしていきながら深さ優先探索により調べる。
ソースコード
int s,n,m[11],t; bool c[40][40]; bool rec(){ int i=0,j=0; for(;i<s;i++)for(j=0;j<s;j++)if(!c[i][j])goto OUT; OUT: if(i>=s)return 1; for(int k=1;k<=10;k++)if(m[k]){ if(i+k>s||j+k>s)continue; rep(y,k)rep(x,k)if(c[i+y][j+x])goto FAIL; rep(y,k)rep(x,k)c[i+y][j+x]=1; m[k]--; if(rec())return 1; m[k]++; rep(y,k)rep(x,k)c[i+y][j+x]=0; FAIL:; } return 0; } int main(){ int T; scanf("%d",&T); rep(U,T){ scanf("%d%d",&s,&n); rep(i,11)m[i]=0; int sum=0,t; rep(i,n)scanf("%d",&t),m[t]++,sum+=t*t; if(sum!=s*s){ puts("HUTUTU!"); continue; } rep(i,s)rep(j,s)c[i][j]=0; puts(rec()?"KHOOOOB!":"HUTUTU!"); } return 0; }