-
Notifications
You must be signed in to change notification settings - Fork 23
/
1020.cpp
89 lines (85 loc) · 1.36 KB
/
1020.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
using namespace std;
int size,a[20],freq[13];
bool cake[40][40],ans;
bool put(const int x,const int y)
{
if(ans)return 1;
int i,j,k;
for(i=2;i<=10;i++)
{
bool b=1;
if(x+i-1>size||y+i-1>size)break;
for(j=1;j<=i;j++)
if(cake[x+i-1][y+j-1])
{
b=0;
break;
}
if(!b)break;
for(j=1;j<i;j++)
if(cake[x+j-1][y+i-1])
{
b=0;
break;
}
if(!b)break;
}
for(i=i-1;i>=1;i--)
{
if(ans)return 1;
if(freq[i]>0)
{
bool found=0;
for(j=1;j<=i;j++)
for(k=1;k<=i;k++)
cake[x+j-1][y+k-1]=1;
freq[i]--;
for(j=x;j<=size;j++)
{
for(k=1;k<=size;k++)
{
if(!cake[j][k])found=1;
if(found)break;
}
if(found)break;
}
if(!found)ans=1;
if(ans)return 1;
put(j,k);
if(ans)return 1;
freq[i]++;
for(j=1;j<=i;j++)
for(k=1;k<=i;k++)
cake[x+j-1][y+k-1]=0;
}
}
if(ans)return 1;
return 0;
}
int main()
{
int t,n,i,j,q,area;
cin>>t;
for(q=1;q<=t;q++)
{
cin>>size>>n;
area=0;
for(i=1;i<=10;i++)
freq[i]=0;
for(i=1;i<=n;i++)
{
cin>>a[i];
freq[a[i]]++;
area+=a[i]*a[i];
}
for(i=1;i<=size;i++)
for(j=1;j<=size;j++)
cake[i][j]=0;
ans=0;
if(area==size*size)ans=put(1,1);
if(ans)cout<<"KHOOOOB!"<<endl;
else cout<<"HUTUTU!"<<endl;
}
return 0;
}