Keengle's Blog

Problem: 1020

User: 

Memory: 24K

Time: 2547MS

Language: Python

Result: Accepted

import sys

d,c,s,n = None,None,None,None

#d  []  :grids have been occupied

def init():

    global d,c,s,n

    d = [0 for i in xrange(s) ]

    c = [0 for i in xrange(11)]

def dfs(a):

    global d,c,s,n

    if a == n :

        return True

    put,p = 100,0

    for i in xrange(s):

        if d[i]<put :

            put,p = d[i],i

    for i in xrange(10,0,-1):

        if c[i]>0 and put+i<=s and p+i<=s :

            f = True

            for j in xrange(p,p+i):

                if d[j] != put :

                    f = False

                    break

            if f :

                for j in xrange(p,p+i):

                    d[j] += i

                c[i] -= 1

                if dfs(a+1) :

                    return True

                c[i] += 1

                for j in xrange(p,p+i):

                    d[j] -= i

    return False

def main():

    global d,c,s,n

    t = input()

    for i in xrange(t):

        data = map(int, sys.stdin.readline().split() )

        area = 0

        s = data[0]

        n = data[1]

        init()

        ok = False

        for j in xrange(2,n+2):

            c[ data[j] ] += 1

            area += data[j] * data[j]

        if area == s*s :

            ok = dfs(0)

        if ok :

            print "KHOOOOB!"

        else :

            print "HUTUTU!"

main()