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;
}