http://acm.pku.edu.cn/JudgeOnline/problem?id=1020
Код:
#include<stdio.h> #include<stdlib.h> #define maxlong 41 int cake[maxlong][maxlong]; int n,size; int small[17]; int use[17]; int ok; int cmp(const void *a,const void *b) { return *(int *)b-*(int *)a; } int searchfirst() { int i,j,temp=1; for(i=1;i<=size;i++) for(j=1;j<=size;j++) {if(cake[i][j]==1) ++temp; else return temp;} return temp; } int valid(int i,int j) { if((i>=1&&i<=size)&&(j>=1&&j<=size)) return 1; else return 0; } int check(int a,int b,int c) { int i,j; if(valid(a+small[c]-1,b+small[c]-1)==0) return 0; for(i=a;i<=a+small[c]-1;i++) for(j=b;j<=b+small[c]-1;j++) if(cake[i][j]==1) return 0; return 1; } void changecake(int indexx,int indexy,int c) { int i,j; for(i=indexx;i<=indexx+small[c]-1;i++) for(j=indexy;j<=indexy+small[c]-1;j++) cake[i][j]=1; } void huanyuan(int indexx,int indexy,int c) { int i,j; for(i=indexx;i<=indexx+small[c]-1;i++) for(j=indexy;j<=indexy+small[c]-1;j++) cake[i][j]=0; } int checkok() { int i; for(i=1;i<=n;i++) if(use[i]==0) return 0; return 1; } void put() { int i,count,indexx,indexy,past=0; if(ok==1) return; count=searchfirst(); indexy=count%size; if(indexy==0) indexy=size; if(count%size==0) indexx=count/size; else indexx=count/size+1; for(i=1;i<=n;i++) { if(past==small[i]) continue; if(use[i]==0) { if(check(indexx,indexy,i)==1) { use[i]=1; changecake(indexx,indexy,i); put(); if(ok==1) return; if(checkok()==1) {ok=1;return;} use[i]=0; huanyuan(indexx,indexy,i); past=small[i]; } } } } int main() { int i,j,t,temp; scanf("%d",&t); while(t--) { scanf("%d%d",&size,&n); temp=0; ok=0; for(i=1;i<=size;i++) for(j=1;j<=size;j++) cake[i][j]=0; for(i=1;i<=n;i++) { use[i]=0; scanf("%d",&small[i]); temp+=small[i]*small[i]; } if(temp!=size*size) {printf("HUTUTU!\n");continue;} qsort(small+1,n,sizeof(small[0]),cmp); put(); if(ok==1) printf("KHOOOOB!\n"); else printf("HUTUTU!\n"); } }