Problem:


>土地分割

 ハウジングメーカーの山田ハウスは、新たな目玉商品として、学校や病院など環境が充実している緑ホームタウンの分譲地を売り出しました。この分譲地は複数の区画に分割されており、好きなだけ購入できますが、購入する区画を合わせた土地の形状は長方形(正方形を含む)でなければなりません。

 山田ハウスは、全区画が完売した分譲地を管理するため購入者ごとに境界線を引き、その区画の 1つに購入者番号を書いた看板を設置しておきました。境界線は地面に木の枝で線を引いただけのものであったため、数日後の豪雨により消えてしまい看板だけが残りました。図 1 は看板のあった区画に、その区画を買った購入者番号を記したものです。これでは分譲地がどのように買われたか分かりません。救いは事務所の引き出しにあった購入者番号 b と購入区画数 k のメモ(図 2)が見つかったことです。

図１（左）：看板の配置、図2（右）：メモ

 プログラマーであるあなたは、プログラムを書いて山田ハウスを助けることになりました。分譲地の大きさ X &times; Y 、購入者数 n 、メモの情報 b、 k 、及び看板の位置情報 s を入力とし、図 3 に示すように各区画の購入者を出力するプログラムを作成してください。

図3：各区画の購入者

与えられた情報について、以下の場合は NA と出力します。

  
 区画を区別する方法が存在しない場合

  
 区画を区別する方法が複数存在する場合

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロが３つの行で示されます。各データセットは以下の形式で与えられます。

X Y n
b1 k1
b2 k2
:
bn kn
s11 s21 ... sX1
s12 s22 ... sX2
:
s1Y s2Y ... sXY

1 行目にX, Y, n (1 ≤ X, Y ≤ 10, 1 ≤ n ≤ 15) が与えられます。続く n 行にメモの i 行目に書かれた情報 bi (1 ≤ bi ≤ n), ki (1 ≤ ki ≤ 100) が与えられます。

続く Y 行に区画情報の i 行目の情報 sij が与えられます。sij はi 行目の左から j 番目の区画の看板情報を表します。看板の情報 sij として、その区画に看板が無い場合は 0 、看板がある場合はその区画の購入者番号が与えられます。

データセットの数は 50  を超えません。

Output

入力データセットごとに、購入者情報またはNA を出力します。

Sample Input

5 4 6
1 6
2 4
3 3
4 4
5 1
6 2
0 0 1 0 0
0 0 0 2 0
0 0 0 3 0
0 4 5 0 6
3 3 1
1 9
0 0 1
0 0 0
0 0 0
4 4 4
1 6
2 2
3 4
4 4
0 1 0 0
0 0 0 2
0 0 3 0
0 4 0 0
0 0 0

Output for the Sample Input

1 1 1 2 2
1 1 1 2 2
4 4 3 3 3
4 4 5 6 6
1 1 1
1 1 1
1 1 1
NA



Sample input:
5 4 6
1 6
2 4
3 3
4 4
5 1
6 2
0 0 1 0 0
0 0 0 2 0
0 0 0 3 0
0 4 5 0 6
3 3 1
1 9
0 0 1
0 0 0
0 0 0
4 4 4
1 6
2 2
3 4
4 4
0 1 0 0
0 0 0 2
0 0 3 0
0 4 0 0
0 0 0


Sample output:
1 1 1 2 2
1 1 1 2 2
4 4 3 3 3
4 4 5 6 6
1 1 1
1 1 1
1 1 1
NA

Submission status: Time Limit Exceeded

Solution code:
import copy

def main(land, b):
    for h in range(H):
        for w in range(W):
            if land[h][w] == b:
                if f1(land, h, w, b, data[land[h][w]]):
                    return
            
def f1(land, h, w, b, k):
    for q in range(1, k+1):
        if k%q == 0:
            if f2(land, h, w, q, k/q, b):
                return True
    else:
        return
        
def f2(land, h, w, r, c, b):
    for _h in range(r):
        for _w in range(c):
            if 0 <= h-_h and 0 <= w-_w:
                if f3(land, h-_h, w-_w, r, c, b):
                    return True
    else:
        return
                
def f3(land, h, w, r, c, b):
    _land = copy.deepcopy(land)
    for _h in range(r):
        for _w in range(c):
            if 0 <= h+_h <= H-1 and 0 <= w+_w <= W-1:
                if _land[h+_h][w+_w] == 0 or _land[h+_h][w+_w] == b:
                    _land[h+_h][w+_w] = b
                else:
                    return
            else:
                return
    else:
        if b < n:
            return main(_land, b+1)
        else:
            for line in _land:
                print ' '.join(map(str, line))
            return True

while True:
    W, H, n = map(int, raw_input().split())
    if H == W == n == 0: break
    data = {}
    for i in range(n):
        b, k = map(int, raw_input().split())
        data[b] = k
    land = [map(int, raw_input().split()) for i in range(H)]
    main(land, 1)

Submission status: Time Limit Exceeded

Solution code:
import copy

def main(land, b):
    for h in range(H):
        for w in range(W):
            if land[h][w] == b:
                if f1(land, h, w, b, data[land[h][w]]):
                    return True
            
def f1(land, h, w, b, k):
    for q in range(1, k+1):
        if k%q == 0:
            if f2(land, h, w, q, k/q, b):
                return True
    else:
        return
        
def f2(land, h, w, r, c, b):
    for _h in range(r):
        for _w in range(c):
            if 0 <= h-_h and 0 <= w-_w:
                if f3(land, h-_h, w-_w, r, c, b):
                    return True
    else:
        return
                
def f3(land, h, w, r, c, b):
    _land = copy.deepcopy(land)
    for _h in range(r):
        for _w in range(c):
            if 0 <= h+_h <= H-1 and 0 <= w+_w <= W-1:
                if _land[h+_h][w+_w] == 0 or _land[h+_h][w+_w] == b:
                    _land[h+_h][w+_w] = b
                else:
                    return
            else:
                return
    else:
        if b < n:
            return main(_land, b+1)
        else:
            for line in _land:
                print ' '.join(map(str, line))
            return True

while True:
    W, H, n = map(int, raw_input().split())
    if H == W == n == 0: break
    data = {}
    for i in range(n):
        b, k = map(int, raw_input().split())
        data[b] = k
    land = [map(int, raw_input().split()) for i in range(H)]
    main(land, 1)

Submission status: Time Limit Exceeded

Solution code:
import copy

def main(land, b):
    for h in range(H):
        for w in range(W):
            if land[h][w] == b:
                if f1(land, h, w, b, data[land[h][w]]):
                    return True
            
def f1(land, h, w, b, k):
    for q in range(1, k+1):
        if k%q == 0:
            if f2(land, h, w, q, k/q, b):
                return True
    else:
        return
        
def f2(land, h, w, r, c, b):
    for _h in range(r):
        for _w in range(c):
            if 0 <= h-_h and 0 <= w-_w:
                if f3(land, h-_h, w-_w, r, c, b):
                    return True
    else:
        return
                
def f3(land, h, w, r, c, b):
    _land = copy.deepcopy(land)
    for _h in range(r):
        for _w in range(c):
            if 0 <= h+_h <= H-1 and 0 <= w+_w <= W-1:
                if _land[h+_h][w+_w] == 0 or _land[h+_h][w+_w] == b:
                    _land[h+_h][w+_w] = b
                else:
                    return
            else:
                return
    else:
        if b < n:
            return main(_land, b+1)
        else:
            for line in _land:
                print ' '.join(map(str, line))
            return True

while True:
    W, H, n = map(int, raw_input().split())
    if H == W == n == 0: break
    data = {}
    for i in range(n):
        b, k = map(int, raw_input().split())
        data[b] = k
    land = [map(int, raw_input().split()) for i in range(H)]
    if not main(land, 1):
        print 'NA'

Submission status: Time Limit Exceeded

Solution code:
import copy

def main(land, b):
    for h in range(H):
        for w in range(W):
            if land[h][w] == b:
                if f1(land, h, w, b, data[land[h][w]]):
                    return True
            
def f1(land, h, w, b, k):
    for q in range(1, k+1):
        if k%q == 0:
            if f2(land, h, w, q, k/q, b):
                return True
    else:
        return
        
def f2(land, h, w, r, c, b):
    for _h in range(r):
        for _w in range(c):
            if 0 <= h-_h and 0 <= w-_w:
                if f3(land, h-_h, w-_w, r, c, b):
                    return True
    else:
        return
                
def f3(land, h, w, r, c, b):
    global ans, count
    _land = copy.deepcopy(land)
    for _h in range(r):
        for _w in range(c):
            if 0 <= h+_h <= H-1 and 0 <= w+_w <= W-1:
                if _land[h+_h][w+_w] == 0 or _land[h+_h][w+_w] == b:
                    _land[h+_h][w+_w] = b
                else:
                    return
            else:
                return
    else:
        if b < n:
            return main(_land, b+1)
        else:
            if count == 0:
                ans = _land
                count = 1
            else:
                ans = None
                return True

while True:
    W, H, n = map(int, raw_input().split())
    if H == W == n == 0: break
    data = {}
    for i in range(n):
        b, k = map(int, raw_input().split())
        data[b] = k
    land = [map(int, raw_input().split()) for i in range(H)]
    ans = None
    count = 0
    main(land, 1)
    if ans:
        for line in ans:
            print ' '.join(map(str, line))
    else:
        print 'NA'

Submission status: Accepted

Solution code:


def putpiece(bitmap,unused,pieces,numans,pcsans,FINFLAG):
    # print(bin(bitmap))
    # print(unused,"***",pieces,"***",numans)
    if FINFLAG:
        return numans,pcsans
    if not unused:
        pcsans = pieces
        return numans + 1, pcsans
    if numans > 1:
        return 2, pieces
    b,k,y,x = unused[-1]
    # print(set([ (k//i,k//(k//i)) for i in range(1,min(X+1,k+1))]))
    for h,w in set([ (k//i,k//(k//i)) for i in range(1,min(X+1,k+1)) if not (k//i)*(k//(k//i)) - k]):
        for pt,qt in product(range(max(0,y-h+1),min(Y-h+1,y+1)),range(max(0,x-w+1),min(X-w+1,x+1))):
            rt,st = pt+h-1, qt+w-1
            piece = 0
            piece2 = 0
            for i in range(st-qt+1): piece |= 1 << i
            for j in range(rt-pt+1): piece2 |= piece << j*X
            piece = piece2
            piece = piece << X-st-1
            piece = piece << (Y-rt-1)*X
            mark = 1
            mark = mark << X-x-1
            mark = mark << (Y-y-1)*X
            if not (bitmap&piece)^mark: numans,pcsans = putpiece(bitmap|piece,unused[:-1],pieces+[[b,k,pt,qt,rt,st]],numans,pcsans,False)
            if numans > 1: return 2, pcsans
        if numans > 1: return 2, pcsans
    else:
        return numans,pcsans


from itertools import product
while(True):
    numans = 0
    pcsans = []
    X,Y,n = map(int,input().split())
    if not X: break
    bk = sorted([list(map(int,input().split())) for _ in range(n)])
    ss = [list(map(int,input().split())) for _ in range(Y)]
    yxs = sorted([ss[i][j],i,j] for i,j in product(range(Y),range(X)) if ss[i][j])
    bkyx = [ bk[i]+yxs[i][1:] for i in range(n)]
    # from pprint import pprint
    # pprint(bk)
    # pprint(ss)
    filled = "".join([ "".join(["1" if ss[i][j] else "0" for j in range(X)]) for i in range(Y)])
    # pprint(filled)
    # pprint([filled[i*X:i*X+X] for i in range(Y)])
    # pprint(bkyx)
    nans,pcs = putpiece(int(filled,2),bkyx,[],0,0,False)
    # print(nans,pcs)
    if nans > 1:
        print("NA")
    elif nans:
        toprint = [[0]*X for _ in range(Y)]
        for i,m,sy,sx,ey,ex in pcs:
            for j in range(sy,ey+1): toprint[j][sx:ex+1] = [i]*(ex-sx+1)
        for a in toprint: print(" ".join(str(b) for b in a))
    else:
        print("NA")
    # print("***********************************::")
    # break


# numans = 0
# mapans = []

# bitmap,[[b1,k1,x1,y1]],[[p,q,r,s]]


# if not len([]):
#  numans += 0
#  mapans = p,q,r,s
#  return None

# pt,qt,rt,st

# if not bitmap & bitpiece
#  bitmap |= bitpeace
#  putpiece(bitmap|bitpiece,[][:-1],[]+[pt,qt,rt,st])

Submission status: Accepted

Solution code:
from itertools import product
# from line_profiler import LineProfiler


def putpiece(X,Y,bitmap,unused,pieces,numans,pcsans,FINFLAG):
    if FINFLAG:
        return numans,pcsans
    if not unused:
        pcsans = pieces
        return numans + 1, pcsans
    if numans > 1:
        return 2, pieces
    b,k,y,x = unused[-1]
    for h,w in set([ (k//i,k//(k//i)) for i in range(1,min(X+1,k+1)) if not (k//i)*(k//(k//i)) - k]):
        for pt,qt in product(range(max(0,y-h+1),min(Y-h+1,y+1)),range(max(0,x-w+1),min(X-w+1,x+1))):
            rt,st = pt+h-1, qt+w-1
            piece = 2**(st-qt+1)-1
            piece2 = 0
            for j in range(rt-pt+1): piece2 |= piece << j*X
            piece = ( piece2 << X-st-1 ) << (Y-rt-1)*X
            mark = ( 1 << X-x-1 ) << (Y-y-1)*X
            if not (bitmap&piece)^mark: numans,pcsans = putpiece(X,Y,bitmap|piece,unused[:-1],pieces+[[b,k,pt,qt,rt,st]],numans,pcsans,False)
            if numans > 1: return 2, pcsans
    else:
        return numans,pcsans

def main():
    while(True):
        X,Y,n = map(int,input().split())
        if not X: break
        bk = sorted([list(map(int,input().split())) for _ in range(n)])
        ss = [list(map(int,input().split())) for _ in range(Y)]
        yxs = sorted([ss[i][j],i,j] for i,j in product(range(Y),range(X)) if ss[i][j])
        bkyx = [ bk[i]+yxs[i][1:] for i in range(n)]
        filled = "".join([ "".join(["1" if ss[i][j] else "0" for j in range(X)]) for i in range(Y)])
        nans,pcs = putpiece(X,Y,int(filled,2),bkyx,[],0,0,False)
        if nans > 1:
            print("NA")
        elif nans:
            toprint = [[0]*X for _ in range(Y)]
            for i,_,sy,sx,ey,ex in pcs:
                for j in range(sy,ey+1): toprint[j][sx:ex+1] = [i]*(ex-sx+1)
            for a in toprint: print(" ".join(str(b) for b in a))
        else:
            print("NA")

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.add_function(putpiece)
    # prf.runcall(main)
    # prf.print_stats()
    main()

Submission status: Accepted

Solution code:
from itertools import product
# from line_profiler import LineProfiler


def putpiece(X,Y,bitmap,unused,pieces,numans,pcsans):
    if not unused: return numans + 1, pieces
    if numans > 1: return 2, pieces
    b,k,y,x = unused[-1]
    for h,w in set([ (k//i,k//(k//i)) for i in range(1,min(X+1,k+1)) if not (k//i)*(k//(k//i)) - k]):
        ps, pe, qs, qe = max(0,y-h+1), min(Y-h+1,y+1), max(0,x-w+1), min(X-w+1,x+1)
        for pt,qt in product(range(ps,pe),range(qs,qe)):
            rt,st = pt+h-1, qt+w-1
            piece = ( sum([2**(st-qt+1)-1 << j*X for j in range(rt-pt+1)]) << X-st-1 ) << (Y-rt-1)*X
            mark = ( 1 << X-x-1 ) << (Y-y-1)*X
            if not (bitmap&piece)^mark:
                numans,pcsans = putpiece(X,Y,bitmap|piece,unused[:-1],pieces+[[b,k,pt,qt,rt,st]],numans,pcsans)
            if numans > 1: return 2, pcsans
    else:
        return numans,pcsans

def main():
    while(True):
        X,Y,n = map(int,input().split())
        if not X: break
        bk = sorted([list(map(int,input().split())) for _ in range(n)])
        ss = [list(map(int,input().split())) for _ in range(Y)]
        yxs = sorted([ss[i][j],i,j] for i,j in product(range(Y),range(X)) if ss[i][j])
        bkyx = [ bk[i]+yxs[i][1:] for i in range(n)]
        filled = "".join([ "".join(["1" if ss[i][j] else "0" for j in range(X)]) for i in range(Y)])
        nans,pcs = putpiece(X,Y,int(filled,2),bkyx,[],0,0)
        if nans > 1:
            print("NA")
        elif nans:
            toprint = [[0]*X for _ in range(Y)]
            for i,_,sy,sx,ey,ex in pcs:
                for j in range(sy,ey+1): toprint[j][sx:ex+1] = [i]*(ex-sx+1)
            for a in toprint: print(" ".join(str(b) for b in a))
        else:
            print("NA")

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.add_function(putpiece)
    # prf.runcall(main)
    # prf.print_stats()
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline


from copy import deepcopy
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
Memo = namedtuple('Memo', 'buyer lot x y')
from itertools import product



def placeable(lots, buyer, x, y, w, h):
    if x < 0 or len(lots[0]) < x + w or y < 0 or len(lots) < y + h:
        return False
    for i, j in product(range(y, y + h), range(x, x + w)):
        if lots[i][j] not in (0, buyer):
            return False
    return True


def place(lots, buyer, x, y, w, h):
    tmp = deepcopy(lots)
    for i, j in product(range(y, y + h), range(x, x + w)):
        tmp[i][j] = buyer
    return tmp


def solve(lots, memos):
    if len(memos) == 0:
        global ans, count
        ans = lots
        count += 1
        return
    m = memos[0]

    for w in range(1, m.lot + 1):
        if m.lot % w:
            continue
        h = m.lot // w
        for y, x in product(range(m.y - h + 1, m.y + 1), range(m.x - w + 1, m.x + 1)):
            if not placeable(lots, m.buyer, x, y, w, h):
                continue
            solve(place(lots, m.buyer, x, y, w, h), memos[1:])


def search_sign(lots, w, h):
    sign = {}
    for y, x in product(range(h), range(w)):
        if lots[y][x]:
            sign[lots[y][x]] = Point(x, y)
    return sign


def main():
    while True:
        w, h, n = map(int, readline().split())
        if w == 0:
            break
        memos = [map(int, readline().split()) for _ in range(n)]
        lots = [list(map(int, readline().split())) for _ in range(h)]
        sign = search_sign(lots, w, h)
        memos = [Memo(b, l, sign[b].x, sign[b].y) for b, l in memos]
        global ans, count
        ans, count = None, 0
        solve(lots, memos)
        if count == 1:
            for ai in ans:
                print(*ai)
        else:
            print('NA')
main()