Problem:


Blur

図 1 のような 10×10 のマス目の「布」があり、（1，2）のようにX座標・Y座標の値の対でマス目を示すことにします。座標値は 0 から始まる整数とします。例えば、図 1 の◎の座標は (1, 2) です。
この「布」に染料を少しずつたらして染物を作ります。たらす染料の滴には「大」「中」「小」の 3 サイズがあり、染料の滴の落ちたマス目を中心に図 1 のように周囲も色がつきます。図 1 で☆が中心、○が色のにじむ範囲です。

「布」は、最初は「まっしろ」つまり、どのマス目も色の濃さを示す値が 0 とします。染料の滴が落ちるごとに値が 1 ずつ増えていきます。「小」が（1, 2）、「中」が（3, 2）に落ちた場合、各マス目の値は図 2 の左のようになります。染料がもったいないので、図 2 の右に示すようなにじむ範囲が布の外にはみ出すような染料の落とし方はしないことになっています。また、同じ場所に複数の染料をたらすこともあります。

このような作業を何回か繰り返した結果、布にすばらしい模様が浮かび上がりましたが、残念なことに、うっかり作業経過を記録し忘れてしまいました。どうにもさっぱり思い出せませんが、かろうじて、落とした染料の滴数は覚えていました。あなたは、すばらしい染物を再現しなければなりません。すばらしい染物のデータを読みこんで、どこに、どのような染料をたらしたかを出力するプログラムを作成してください。なお、落とした染料の滴数は 12 以下とします。

入力

入力の形式は以下のとおりです：

最初の 1 行に落とした染料の滴数 n が与えられます。次の行から 10 行に各座標の色の濃さが空白区切りで与えられます。

出力

出力は n 行からなります。染料の滴の「大」を 3、「中」を 2、「小」を 1 で表し、落とした染料ごとに、そのX座標、Y座標、滴の大きさを空白で区切って1行に出力してください。

染料のたらし方はどのような順番で出力しても良いものとします。

入力例1

2
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 1 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

出力例1

3 2 1
8 4 2

入力例2

6
0 0 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 0 0
0 0 1 1 1 3 1 1 0 0
0 0 1 1 3 1 1 1 0 0
0 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 1 0 0

出力例2

2 2 3
7 7 3
6 3 2
3 6 2
4 4 1
5 5 1



Sample input:
2
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 1 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0


Sample output:
3 2 1
8 4 2

Submission status: Runtime Error

Solution code:
n_drop, cloth = int(input()), [[int(i) for i in input().split()] for _ in range(10)]
n_stain = sum(sum(i) for i in cloth)
n = (n_stain - 5 * n_drop) // 4

drops_candidate = []
dl = 0
while 2 * dl <= n:
    dm = n - 2 * dl
    ds = n_drop - dm - dl
    if ds >= 0:
        drops_candidate.append([ds, dm, dl])
    dl += 1

dx = (0, -1, 1, 0, 0, -1, -1, 1, 1, -2, 2, 0, 0)
dy = (0, 0, 0, -1, 1, -1, 1, -1, 1, 0, 0, -2, 2)
dd = (5, 9, 13)
min_range = (0, 0, 1)


def find(cloth, drops, pointer):
    global dy, dx
    for d in range(3):
        if not drops[d]:
            continue
        dn, ps, mir = dd[d], pointer if pointer else 11, 0 if d < 2 else 1
        mar = 9 - mir
        for p in range(ps, 89):
            x, y = p % 10, p // 10
            if not mir < x < mar or not mir < y < mar:
                continue
            for i in range(dn):
                if not cloth[y + dy[i]][x + dx[i]]:
                    break
            else:
                for i in range(dn):
                    cloth[y + dy[i]][x + dx[i]] -= 1
                drops[d] -= 1
                if sum(drops):
                    result = find(cloth, drops, p)
                    if result:
                        result.append((x, y, d + 1))
                        return result
                    else:
                        for i in range(dn):
                            cloth[y + dy[i]][x + dx[i]] += 1
                        drops[d] += 1
                else:
                    return [(x, y, d + 1)]
    return False


for drops in drops_candidate:
    history = find(cloth, drops, 0)
    if history != False:
        for h in history:
            print(*h)
        break

Submission status: Runtime Error

Solution code:
n_drop, cloth = int(input()), [[int(i) for i in input().split()] for _ in range(10)]
n_stain = sum(sum(i) for i in cloth)
n = (n_stain - 5 * n_drop) // 4

drops_candidate = []
dl = 0
while 2 * dl <= n:
    dm = n - 2 * dl
    ds = n_drop - dm - dl
    if ds >= 0:
        drops_candidate.append([ds, dm, dl])
    dl += 1

dx = (0, -1, 1, 0, 0, -1, -1, 1, 1, -2, 2, 0, 0)
dy = (0, 0, 0, -1, 1, -1, 1, -1, 1, 0, 0, -2, 2)
dd = (5, 9, 13)


def find(cloth, drops, pointer):
    global dy, dx, dd
    for p in range(pointer, 100):
        if cloth[p // 10][p % 10]:
            break
        pointer += 1
    for d in range(3):
        if not drops[d]:
            continue
        dn = dd[d]
        for i in range(dn):
            x, y = pointer % 10 + dx[i], pointer // 10 + dy[i]
            for j in range(dn):
                if not cloth[y + dy[j]][x + dx[j]]:
                    break
            else:
                for j in range(dn):
                    cloth[y + dy[j]][x + dx[j]] -= 1
                drops[d] -= 1
                if sum(drops):
                    result = find(cloth, drops, p)
                    if result:
                        result.append((x, y, d + 1))
                        return result
                    for i in range(dn):
                        cloth[y + dy[i]][x + dx[i]] += 1
                    drops[d] += 1
                else:
                    return [(x, y, d + 1)]
    return False


for drops in drops_candidate:
    history = find(cloth, drops, 0)
    if history != False:
        for h in history:
            print(*h)
        break

Submission status: Runtime Error

Solution code:
import itertools

dx = (0, 0, 0, 1,-1, 1, 1,-1,-1,-2, 2, 0, 0)
dy = (0, 1,-1, 0, 0, 1,-1, 1,-1, 0, 0,-2, 2)
dd = (5, 9, 13)

def drop(fab, used, size_list):
    for xy in range(100):
        y = xy%10
        x = xy//10
        size = size_list[used]
        check = True
        for i in range(size):
            if fab[y + dy[i] + 2][x + dx[i] + 2] == 0:
                check = False
        if check:
            for i in range(size):
                fab[y + dy[i] + 2][x + dx[i] + 2] -= 1
            if sum(map(sum, fab)):
                result = drop(fab, used + 1, size_list)
                if result:
                    result.append([x, y, dd.index(size) + 1])
                    return result
                for i in range(size):
                    fab[y + dy[i] + 2][x + dx[i] + 2] += 1
            else:
                return [[x, y, dd.index(size) + 1]]
    return False

fab = [[0 for i in range(14)] for j in range(14)]

n = int(input())

for i in range(10):
    fab[i + 2][2:12] = list(map(int, input().split()))

s = sum(map(sum, fab))
d_all = list(itertools.combinations_with_replacement([5,9,13], n))
d_list = [l for l in d_all if sum(l) == s]

ans = [0 for i in range(n)]
for d in d_list:
    d_tmp = sorted(d)[::-1]
    ans = drop(fab, 0, d_tmp)
    if ans:
        for a in ans:
            print(*a)
        break

Submission status: Runtime Error

Solution code:
import itertools

dx = (0, 0, 0, 1,-1, 1, 1,-1,-1,-2, 2, 0, 0)
dy = (0, 1,-1, 0, 0, 1,-1, 1,-1, 0, 0,-2, 2)
dd = (5, 9, 13)

def drop(fab, used, size_list):
    for xy in range(100):
        y = xy%10
        x = xy//10
        size = size_list[used]
        check = True
        for i in range(size):
            if fab[y + dy[i] + 2][x + dx[i] + 2] == 0:
                check = False
        if check:
            for i in range(size):
                fab[y + dy[i] + 2][x + dx[i] + 2] -= 1
            if sum(map(sum, fab)):
                result = drop(fab, used + 1, size_list)
                if result:
                    result.append([x, y, dd.index(size) + 1])
                    return result
                for i in range(size):
                    fab[y + dy[i] + 2][x + dx[i] + 2] += 1
            else:
                return [[x, y, dd.index(size) + 1]]
    return False

fab = [[0 for i in range(14)] for j in range(14)]

n = int(input())

for i in range(10):
    fab[i + 2][2:12] = list(map(int, input().split()))

s = sum(map(sum, fab))
d_all = list(itertools.combinations_with_replacement([5,9,13], n))
d_list = [l for l in d_all if sum(l) == s]

ans = [0 for i in range(n)]
for d in d_list:
#    d_tmp = sorted(d)[::-1]
    d_tmp = d
    ans = drop(fab, 0, d_tmp)
    if ans:
        for a in ans:
            print(*a)
        break

Submission status: Runtime Error

Solution code:
import itertools

dx = (0, 0, 0, 1,-1, 1, 1,-1,-1,-2, 2, 0, 0)
dy = (0, 1,-1, 0, 0, 1,-1, 1,-1, 0, 0,-2, 2)
dd = (5, 9, 13)

def drop(fab, used, size_list):
    for xy in range(100):
        y = xy%10
        x = xy//10
        size = size_list[used]
        check = True
        for i in range(size):
            if fab[y + dy[i] + 2][x + dx[i] + 2] == 0:
                check = False
                break
        if check:
            for i in range(size):
                fab[y + dy[i] + 2][x + dx[i] + 2] -= 1
            if sum(map(sum, fab)):
                result = drop(fab, used + 1, size_list)
                if result:
                    result.append([x, y, dd.index(size) + 1])
                    return result
                for i in range(size):
                    fab[y + dy[i] + 2][x + dx[i] + 2] += 1
            else:
                return [[x, y, dd.index(size) + 1]]
    return False

fab = [[0 for i in range(14)] for j in range(14)]

n = int(input())

for i in range(10):
    fab[i + 2][2:12] = list(map(int, input().split()))

s = sum(map(sum, fab))
d_all = list(itertools.combinations_with_replacement([5,9,13], n))
d_list = [l for l in d_all if sum(l) == s]

ans = [0 for i in range(n)]
for d in d_list:
    d_tmp = sorted(d)[::-1]
    ans = drop(fab, 0, d_tmp)
    if ans:
        for a in ans:
            print(*a)
        break

Submission status: Runtime Error

Solution code:
import itertools

dx = (0, 0, 0, 1,-1, 1, 1,-1,-1,-2, 2, 0, 0)
dy = (0, 1,-1, 0, 0, 1,-1, 1,-1, 0, 0,-2, 2)
dd = (5, 9, 13)

def drop(fab, start, used, size_list):
    for xy in range(start, 100):
        y = xy%10
        x = xy//10
        size = size_list[used]
        check = True
        for i in range(size):
            if fab[y + dy[i] + 2][x + dx[i] + 2] == 0:
                check = False
                break
        if check:
            for i in range(size):
                fab[y + dy[i] + 2][x + dx[i] + 2] -= 1
            if sum(map(sum, fab)):
                if size == size_list[used + 1]:
                    result = drop(fab, start + 2, used + 1, size_list)
                else:
                    result = drop(fab, 0, used + 1, size_list)
                if result:
                    result.append([x, y, dd.index(size) + 1])
                    return result
                for i in range(size):
                    fab[y + dy[i] + 2][x + dx[i] + 2] += 1
            else:
                return [[x, y, dd.index(size) + 1]]
    return False

fab = [[0 for i in range(14)] for j in range(14)]

n = int(input())

for i in range(10):
    fab[i + 2][2:12] = list(map(int, input().split()))

s = sum(map(sum, fab))
d_all = list(itertools.combinations_with_replacement([5,9,13], n))
d_list = [l for l in d_all if sum(l) == s]

ans = [0 for i in range(n)]
for d in d_list:
    d_tmp = sorted(d)[::-1]
    ans = drop(fab, 0, 0, d_tmp)
    if ans:
        for a in ans:
            print(*a)
        break

Submission status: Runtime Error

Solution code:
import unknown

Submission status: Runtime Error

Solution code:
import itertools
S,M,L = 5,9,13
ref = {5:1,9:2,13:3}
dx = [0, 0, 1, 0,-1, 1, 1,-1,-1, 2, 0,-2, 0]
dy = [0,-1, 0, 1, 0,-1, 1, 1,-1, 0, 2, 0,-2]

def minus(C,x,y,size):
	for i in range(size):
		try: C[y+dy[i]][x+dx[i]] -= 1
		except: pass

def canMinus(C,x,y,size):
	for i in range(size):
		try:
			if C[y+dy[i]][x+dx[i]] == 0:
				return False
		except: pass
	return True

def canMinusList(C,size):
	ls = []
	for y in range(10):
		for x in range(10):
			if canMinus(C,x,y,size):
				ls.append([x,y])
	return ls

def copy(C):
	C_copy = [C[i][:] for i in range(len(C))]
	return C_copy

def tryFindAns(Cloth,drop,p,Rslt):
	size,num = drop[p][0],drop[p][1]
	canList = canMinusList(Cloth,size)
	for comb in itertools.combinations(canList,num):
		rslt = copy(Rslt)
		C = copy(Cloth)
		for x,y in comb:
			if  canMinus(C,x,y,size):
				minus(C,x,y,size)
				rslt.append([x,y,size])
			else:
				break
		else:
			if p+1 == len(drop):
				return rslt
			else:
				return tryFindAns(C,drop,p+1,rslt)

def findAns(Cloth,drop):
	for i in range(2,-1,-1):
		if drop[i][1] == 0:
			drop.pop(i)
	p,rslt = 0,[]
	return tryFindAns(Cloth,drop,p,rslt)

n = int(raw_input())
Cloth = [map(int, raw_input().split()) for i in range(10)]
sm = sum([sum(Cloth[i]) for i in range(10)])
dropList = []

for s in range(n):
	m4 = 13*n-sm-8*s
	if m4 < 0: break
	if m4%4 == 0:
		m = m4/4
		if s+m <= n:
			dropList.append([[13,n-s-m],[9,m],[5,s]])

for drop in dropList:
	ans = findAns(Cloth,drop)
	if ans is not None:
		break

for a in ans:
	print  a[0],a[1],ref[a[2]]

Submission status: Runtime Error

Solution code:
import itertools
S,M,L = 5,9,13
ref = {5:1,9:2,13:3}
dx = [0, 0, 1, 0,-1, 1, 1,-1,-1, 2, 0,-2, 0]
dy = [0,-1, 0, 1, 0,-1, 1, 1,-1, 0, 2, 0,-2]

def minus(C,x,y,size):
	for i in range(size):
		try: C[y+dy[i]][x+dx[i]] -= 1
		except: pass

def canMinus(C,x,y,size):
	for i in range(size):
		try:
			if C[y+dy[i]][x+dx[i]] == 0:
				return False
		except: pass
	return True

def canMinusList(C,size):
	ls = []
	for y in range(10):
		for x in range(10):
			if canMinus(C,x,y,size):
				ls.append([x,y])
	return ls

def copy(C):
	C_copy = [C[i][:] for i in range(len(C))]
	return C_copy

def tryFindAns(Cloth,drop,p,Rslt):
	size,num = drop[p][0],drop[p][1]
	canList = canMinusList(Cloth,size)
	for comb in itertools.combinations(canList,num):
		rslt = copy(Rslt)
		C = copy(Cloth)
		for x,y in comb:
			if  canMinus(C,x,y,size):
				minus(C,x,y,size)
				rslt.append([x,y,size])
			else:
				break
		else:
			if p+1 == len(drop):
				return rslt
			else:
				rslt = tryFindAns(C,drop,p+1,rslt)
		if rslt is not None and len(rslt) == n: return rslt

def findAns(Cloth,drop):
	for i in range(2,-1,-1):
		if drop[i][1] == 0:
			drop.pop(i)
	p,rslt = 0,[]
	return tryFindAns(Cloth,drop,p,rslt)

n = int(raw_input())
Cloth = [map(int, raw_input().split()) for i in range(10)]
sm = sum([sum(Cloth[i]) for i in range(10)])
dropList = []

for s in range(n):
	m4 = 13*n-sm-8*s
	if m4 < 0: break
	if m4%4 == 0:
		m = m4/4
		if s+m <= n:
			dropList.append([[13,n-s-m],[9,m],[5,s]])

for drop in dropList:
	ans = findAns(Cloth,drop)
	if ans is not None:
		break

for a in ans:
	print  a[0],a[1],ref[a[2]]

Submission status: Runtime Error

Solution code:
import itertools
ref = {5:1,9:2,13:3}
dx = [0, 0, 1, 0,-1, 1, 1,-1,-1, 2, 0,-2, 0]
dy = [0,-1, 0, 1, 0,-1, 1, 1,-1, 0, 2, 0,-2]

def isOn(x,y):
    return 0<=x<10 and 0<=y<10

def minus(C,x,y,size):
    for i in range(size):
        C[y+dy[i]][x+dx[i]] -= 1

def plus(C,x,y,size):
    for i in range(size):
        C[y+dy[i]][x+dx[i]] += 1

def canMinus(C,x,y,size):
    return all([isOn(x+dx[i],y+dy[i]) and C[y+dy[i]][x+dx[i]]>0 for i in range(size)])

def findAns(C,drops,k,sp):
    if k == len(drops):
        return []
    for i in range(sp,100):
        if C[i/10][i%10] > 0:
            break
        sp += 1
    for drop in drops:
        size = drop[0]
        for i in range(size):
            sx,sy = sp%10+dx[i],sp/10+dy[i]
            if isOn(sx,sy) and C[sy][sx] > 0:
                if canMinus(C,sx,sy,size):
                    minus(C,sx,sy,size)
                    drops[k][1] -= 1
                    pk=1 if drops[k][1] == 0 else 0
                    ans = findAns(C,drops,k+pk,sp)
                    if ans != False:
                        ans.append([sx,sy,size])
                        return ans
                    drops[k][1] += 1
                    plus(C,sx,sy,size)
    return False

n = int(raw_input())
C = [map(int, raw_input().split()) for i in range(10)]
sm = sum([sum(C[i]) for i in range(10)])
dropList = []
for s in range(n):
    m4 = 13*n-sm-8*s
    if m4 < 0: break
    if m4%4 == 0:
        m = m4/4
        if s+m <= n:
            dropList.append([[13,n-s-m],[9,m],[5,s]])
for drops in dropList:
    for i in range(2,-1,-1):
        if drops[i][1] == 0:
            drops.pop(i)
    ans = findAns(C,drops,0,0)
    if ans != False:
        break
for a in ans:
    print  a[0],a[1],ref[a[2]]

Submission status: Runtime Error

Solution code:
import itertools
ref = {5:1,9:2,13:3}
dx = [0, 0, 1, 0,-1, 1, 1,-1,-1, 2, 0,-2, 0]
dy = [0,-1, 0, 1, 0,-1, 1, 1,-1, 0, 2, 0,-2]

def isOn(x,y):
    return 0<=x<10 and 0<=y<10

def minus(C,x,y,size):
    for i in range(size):
        C[y+dy[i]][x+dx[i]] -= 1

def plus(C,x,y,size):
    for i in range(size):
        C[y+dy[i]][x+dx[i]] += 1

def canMinus(C,x,y,size):
    return all([isOn(x+dx[i],y+dy[i]) and C[y+dy[i]][x+dx[i]]>0 for i in range(size)])

def findAns(C,drops,k,sp):
    if k == len(drops):
        return []
    for i in range(sp,100):
        if C[i/10][i%10] > 0:
            break
        sp += 1
    for drop in drops:
        size = drop[0]
        if drop[1] != 0:
            for i in range(size):
                sx,sy = sp%10+dx[i],sp/10+dy[i]
                if isOn(sx,sy) and C[sy][sx] > 0:
                    if canMinus(C,sx,sy,size):
                        minus(C,sx,sy,size)
                        drops[k][1] -= 1
                        pk=1 if drops[k][1] == 0 else 0
                        ans = findAns(C,drops,k+pk,sp)
                        if ans != False:
                            ans.append([sx,sy,size])
                            return ans
                        drops[k][1] += 1
                        plus(C,sx,sy,size)
    return False

n = int(raw_input())
C = [map(int, raw_input().split()) for i in range(10)]
sm = sum([sum(C[i]) for i in range(10)])
dropList = []
for s in range(n):
    m4 = 13*n-sm-8*s
    if m4 < 0: break
    if m4%4 == 0:
        m = m4/4
        if n-s-m >= 0:
            dropList.append([[13,n-s-m],[9,m],[5,s]])
for drops in dropList:
    for i in range(2,-1,-1):
        if drops[i][1] == 0:
            drops.pop(i)
    ans = findAns(C,drops,0,0)
    if ans != False:
        break
for a in ans:
    print  a[0],a[1],ref[a[2]]