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

дистанційна підтримка освіти школярів


Ежегодный пирог
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");
}
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)