Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#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"); 
	 }
}