#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <string.h> #include <stdio.h> using namespace std; bool IsValid(int index, int s, bool map[][40], int size) { int x = index / s; int y = index % s; if (x + size > s || y + size > s) return false; for (int i = x; i < x + size; i++) for (int j = y; j < y + size; j++) if (map[x][j] == true) return false; return true; } bool DFS(int index, int s, bool map[][40], int n, int size[], bool used[]) { if (index >= s * s) return true; int x = index / s; int y = index % s; if (map[x][y] == true) return DFS(index + 1, s, map, n, size, used); bool failed[16]; memset(failed, false, sizeof(failed)); for (int i = 0; i < n; i++) if (used[i] != true && failed[size[i]] != true) if (IsValid(index, s, map, size[i])) { // map set to true for (int j = x; j < x + size[i]; j++)for (int k = y; k < y + size[i]; k++) map[j][k] = true; used[i] = true; if (DFS(index + 1, s, map, n, size, used))return true; elsefailed[size[i]] = true; used[i] = false; // map set to false for (int j = x; j < x + size[i]; j++)for (int k = y; k < y + size[i]; k++) map[j][k] = false; } else { failed[size[i]] = true; } return false; } int main() { int t, s, n; bool map[40][40]; int size[16]; bool used[16]; cin >> t; while (t--) { cin >> s >> n; for (int i = 0; i < n; i++) cin >> size[i]; memset(map, false, sizeof(map)); memset(used, false, sizeof(used)); int total = 0; for (int i = 0; i < n; i++) total += size[i] * size[i]; if (total != s * s) cout << "HUTUTU!n"; else { if (DFS(0, s, map, n, size, used)) cout << "KHOOOOB!n"; else cout << "HUTUTU!n"; } } }
