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: Wrong Answer

Solution code:
from copy import deepcopy

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

sdxy = ((0, 0), (-1, 0), (1, 0), (0, -1), (0, 1))
mdxy = sdxy + ((-1, -1), (-1, 1), (1, -1), (1, 1))
ldxy = mdxy + ((-2, 0), (2, 0), (0, -2), (0, 2))
dxys = (sdxy, mdxy, ldxy)


def remove(cloth, x, y, drop_size):
    if drop_size == 2 and (not 1 < x < 8 or not 1 < y < 8):
        return False

    for dxy in dxys[drop_size]:
        (dx, dy) = dxy
        if cloth[x + dx][y + dy]:
            cloth[x + dx][y + dy] -= 1
        else:
            return False
    return True


def find(cloth, drops, history):
    for d in range(3):
        if not drops[d]:
            continue
        for j in range(1, 9):
            for i in range(1, 9):
                new_cloth = [r[:] for r in cloth]
                result = remove(new_cloth, i, j, d)

                if result:
                    new_drops, new_history = drops[:], history[:]
                    new_drops[d] -= 1
                    new_history.append((i, j, d + 1))
                    if sum(new_drops):
                        result = find(new_cloth, new_drops, new_history)
                        if result:
                            return result
                    else:
                        return new_history
    return False


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

Submission status: Wrong Answer

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]
        for i in range(size):
            if not fab[y + dy[i] + 2][x + dx[i] + 2]:
                break
        else:
            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, xy + 1, 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: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import combinations, product
import copy


def check(area):
    for y, x in product(range(10), repeat=2):
        if area[y][x] < 0:
            return False
        if area[y][x] == 0:
            continue
        if ((y == 0 or area[y-1][x] < 1) and
                (y == 9 or area[y+1][x] < 1) and
                (x == 0 or area[y][x-1] < 1) and
                (x == 9 or area[y][x+1] < 1)):
            return False
        #"""
        result = False
        if (0 < y and 0 < x < 9 and area[y-1][x-1] > 0 and
                area[y-1][x] > 0 and area[y-1][x+1] > 0 and
                area[y][x-1] == 0 and area[y][x+1] == 0):
            result = True
        elif (0 < y < 9 and x < 9 and area[y-1][x] == 0 and
                area[y-1][x+1] > 0 and area[y][x+1] > 0 and
                area[y+1][x] == 0 and area[y+1][x+1] > 0):
            result = True
        elif (y < 9 and 0 < x < 9 and area[y][x-1] == 0 and
                area[y][x+1] == 0 and area[y+1][x-1] > 0 and
                area[y+1][x] > 0 and area[y+1][x+1] > 0):
            result = True
        elif (0 < y < 9 and 0 < x and area[y-1][x-1] > 0 and
                area[y-1][x] == 0 and area[y][x-1] > 0 and
                area[y+1][x-1] > 0 and area[y+1][x] == 0):
            result = True
        elif (0 < y and 0 < x and area[y-1][x-1] > 0 and
                area[y-1][x] > 0 and area[y][x-1] > 0):
            result = True
        elif (0 < y and x < 9 and area[y-1][x] > 0 and
                area[y-1][x+1] > 0 and area[y][x+1] > 0):
            result = True
        elif (y < 9 and x < 9 and area[y][x+1] > 0 and
                area[y+1][x] > 0 and area[y+1][x+1] > 0):
            result = True
        elif (y < 9 and 0 < x and area[y][x-1] > 0 and
                area[y+1][x-1] > 0 and area[y+1][x] > 0):
            result = True
        elif (0 < y < 9 and 0 < x < 9 and area[y-1][x-1] == 0 and
                area[y-1][x] > 0 and area[y-1][x+1] == 0 and
                area[y][x-1] > 0 and area[y][x+1] > 0 and
                area[y+1][x-1] == 0 and area[y+1][x] > 0 and 
                area[y+1][x+1] == 0):
            result = True
        if not result:
            return False
        #"""
    return True


def can_drop(area, x, y):
    result = []

    if x < 1 or 8 < x or y < 1 or 8 < y:
        return result

    #"""
    test = copy.deepcopy(area)
    ran = ((y-1, x), (y, x-1), (y, x), (y, x+1), (y+1, x))
    if all(area[a][b] > 0 for a, b in ran):
        for a, b in ran:
            test[a][b] -= 1
        if check(test):
            result.append(1)

    ran = ((y-1, x-1), (y-1, x+1), (y+1, x-1), (y+1, x+1))
    if all(area[a][b] > 0 for a, b in ran):
        for a, b in ran:
            test[a][b] -= 1
        if check(test):
            result.append(2)

    if 1 < x < 8 and 1 < y < 8:
        ran = ((y-2, x), (y, x-2), (y, x+2), (y+2, x))
        if all(area[a][b] > 0 for a, b in ran):
            for a, b in ran:
                test[a][b] -= 1
            if check(test):
                result.append(3)
    return result


def drop(area, x, y, size, delta=+1):
    area[y-1][x] += delta
    area[y][x-1] += delta
    area[y][x] += delta
    area[y][x+1] += delta
    area[y+1][x] += delta
    if size < 2:
        return
    area[y-1][x-1] += delta
    area[y-1][x+1] += delta
    area[y+1][x-1] += delta
    area[y+1][x+1] += delta
    if size < 3:
        return
    area[y-2][x] += delta
    area[y][x-2] += delta
    area[y][x+2] += delta
    area[y+2][x] += delta


num_drop = int(stdin.readline())
area = []
for line in stdin:
    area.append([int(d) for d in line.split()])
    print(area[-1])

locations = []
for y in range(10):
    for x in range(10):
        if area[y][x]:
            for size in can_drop(area, x, y):
                locations.append((x, y, size))


locations.sort(key=lambda (x, y, size): size, reverse=True)

b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
test = copy.deepcopy(area)
esl = []
for lcs in combinations(locations, num_drop):
    ff = True
    for dp in esl:
        if dp in lcs:
            ff = False
            break
    if not ff:
        continue
    tt = copy.deepcopy(test)
    for x, y, size in lcs:
        drop(tt, x, y, size, -1)
    if not check(tt):
        esl.append((x, y, size))
        continue
    test = tt
    locations = [(x, y, s) for x, y, s in locations if test[y][x] < 1]
    if all(a == b for a in test):
        for s in lcs:
            print(*s)
        break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import combinations, product
import copy


def check(area):
    for y, x in product(range(10), repeat=2):
        if area[y][x] < 0:
            return False
        if area[y][x] == 0:
            continue
        if ((y == 0 or area[y-1][x] < 1) and
                (y == 9 or area[y+1][x] < 1) and
                (x == 0 or area[y][x-1] < 1) and
                (x == 9 or area[y][x+1] < 1)):
            return False
        #"""
        result = False
        if (0 < y and 0 < x < 9 and area[y-1][x-1] > 0 and
                area[y-1][x] > 0 and area[y-1][x+1] > 0 and
                area[y][x-1] == 0 and area[y][x+1] == 0):
            result = True
        elif (0 < y < 9 and x < 9 and area[y-1][x] == 0 and
                area[y-1][x+1] > 0 and area[y][x+1] > 0 and
                area[y+1][x] == 0 and area[y+1][x+1] > 0):
            result = True
        elif (y < 9 and 0 < x < 9 and area[y][x-1] == 0 and
                area[y][x+1] == 0 and area[y+1][x-1] > 0 and
                area[y+1][x] > 0 and area[y+1][x+1] > 0):
            result = True
        elif (0 < y < 9 and 0 < x and area[y-1][x-1] > 0 and
                area[y-1][x] == 0 and area[y][x-1] > 0 and
                area[y+1][x-1] > 0 and area[y+1][x] == 0):
            result = True
        elif (0 < y and 0 < x and area[y-1][x-1] > 0 and
                area[y-1][x] > 0 and area[y][x-1] > 0):
            result = True
        elif (0 < y and x < 9 and area[y-1][x] > 0 and
                area[y-1][x+1] > 0 and area[y][x+1] > 0):
            result = True
        elif (y < 9 and x < 9 and area[y][x+1] > 0 and
                area[y+1][x] > 0 and area[y+1][x+1] > 0):
            result = True
        elif (y < 9 and 0 < x and area[y][x-1] > 0 and
                area[y+1][x-1] > 0 and area[y+1][x] > 0):
            result = True
        elif (0 < y < 9 and 0 < x < 9 and area[y-1][x-1] == 0 and
                area[y-1][x] > 0 and area[y-1][x+1] == 0 and
                area[y][x-1] > 0 and area[y][x+1] > 0 and
                area[y+1][x-1] == 0 and area[y+1][x] > 0 and
                area[y+1][x+1] == 0):
            result = True
        if not result:
            return False
        #"""
    return True


def can_drop(area, x, y):
    result = []

    if x < 1 or 8 < x or y < 1 or 8 < y:
        return result

    #"""
    test = copy.deepcopy(area)
    ran = ((y-1, x), (y, x-1), (y, x), (y, x+1), (y+1, x))
    if all(area[a][b] > 0 for a, b in ran):
        for a, b in ran:
            test[a][b] -= 1
        if check(test):
            result.append(1)

    ran = ((y-1, x-1), (y-1, x+1), (y+1, x-1), (y+1, x+1))
    if all(area[a][b] > 0 for a, b in ran):
        for a, b in ran:
            test[a][b] -= 1
        if check(test):
            result.append(2)

    if 1 < x < 8 and 1 < y < 8:
        ran = ((y-2, x), (y, x-2), (y, x+2), (y+2, x))
        if all(area[a][b] > 0 for a, b in ran):
            for a, b in ran:
                test[a][b] -= 1
            if check(test):
                result.append(3)
    return result


def drop(area, x, y, size, delta=+1):
    area[y-1][x] += delta
    area[y][x-1] += delta
    area[y][x] += delta
    area[y][x+1] += delta
    area[y+1][x] += delta
    if size < 2:
        return
    area[y-1][x-1] += delta
    area[y-1][x+1] += delta
    area[y+1][x-1] += delta
    area[y+1][x+1] += delta
    if size < 3:
        return
    area[y-2][x] += delta
    area[y][x-2] += delta
    area[y][x+2] += delta
    area[y+2][x] += delta


num_drop = int(stdin.readline())
area = []
for line in stdin:
    area.append([int(d) for d in line.split()])
    #print(area[-1])

locations = []
for y in range(10):
    for x in range(10):
        if area[y][x]:
            for size in can_drop(area, x, y):
                locations.append((x, y, size))


locations.sort(key=lambda (x, y, size): size, reverse=True)
"""
print(locations)
exit()
#"""
b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
test = copy.deepcopy(area)
esl = []
for lcs in combinations(locations, num_drop):
    ff = True
    for dp in esl:
        if dp in lcs:
            ff = False
            break
    if not ff:
        continue
    tt = copy.deepcopy(test)
    for x, y, size in lcs:
        drop(tt, x, y, size, -1)
    if not check(tt):
        esl.append((x, y, size))
        continue
    test = tt
    locations = [(x, y, s) for x, y, s in locations if test[y][x] < 1]
    if all(a == b for a in test):
        for s in lcs:
            print(*s)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8
#from sys import stdin
import time
#import itertools,sys
#import time,copy
#import math
#from math import factorial
#from itertools import product, permutations
#NUM="0123456789"
#A2Z="abcdefghijklmnopqrstuvwxyz"
#import math,sys,time
#import numpy as np

#from q000 import xxxx

# coding: utf-8

#Q042 Coded triangle numbers
import math,sys,time

def read_data():
#  f=open('in.txt')
#  n=int(f.readline())
  n=input()
  x=[]
#  for line in f:
#    x.append(map(int,line.split()))
  for i in range(10):
    x.append(map(int,raw_input().split()))
  return n, x

def is_area3(x,y):
  if x>7 or y>5: return False
  for dx in [0,1,2,1,0]:
    A = P[y][x-dx:x+dx+1]
    if A.count(0)>0: return False
    y += 1
  return True
      
def is_area2(x,y):
  if x>7 or y>7: return False
  for dy in [0,1,2]:
    A = P[y+dy][x:x+3]
    if A.count(0)>0: return False
  return True

def is_area1(x,y):
  if x>8 or y>7: return False
  for dx in [0, 1, 0]:
    A = P[y][x-dx:x+dx+1]
    if A.count(0)>0: return False
    y += 1
  return True

def ink(x,y,s,m):
  global P
  for dy,dx in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
    P[y+dy][x+dx]+=m
  if s==1: return
  for dy,dx in [[1,1],[1,-1],[-1,1],[-1,-1]]:
    P[y+dy][x+dx]+=m
  if s==2: return
  for dy,dx in [[2,0],[-2,0],[0,2],[0,-2]]:
    P[y+dy][x+dx]+=m
  return

drops, P = read_data()
M=[]
i=-1
step =3
while i<99:
  i+=1
  y = i / 10
  x = i % 10
  if P[y][x]==0: continue
#  print
#  print "i=",i
#  print "Pi=",P
#  print "Mi=",M

  if step==3:
#    print "step 3"
    while is_area3(x,y):
      M.append([x,y,3])
      ink(x,y+2,3,-1)
    if P[y][x]==0:
      step = 3
#      print "Po=",P
#      print "Mo=",M
      continue
    else: step = 2

  if step==2:
#    print "step 2"
    while is_area2(x,y):
      M.append([x,y,2])
      ink(x+1,y+1,2,-1)
    if P[y][x]==0:
      step = 3
#      print "Po=",P
#      print "Mo=",M
      continue
    else: step = 1

  if step==1:
#    print "step 1"
    while is_area1(x,y):
      M.append([x,y,1])
      ink(x,y+1,1,-1)
    if P[y][x]==0:
      step = 3
#      print "Po=",P
#      print "Mo=",M
      continue
    else: step = 0

  dx=0
  dy=1
  if step==0 and len(M)>0:
    x,y,tmp = M.pop()
    if tmp==3: dy=2
    elif tmp==2: dx=1
    ink(x+dx,y+dy,tmp,1)
    i = y*10+x-1
    step = tmp-1
  else:
#    print "unsolvable"
    break
#  print "changed io=",i+1
#  print "Mo=",M
#  print "Po=",P
#  print
if drops <=12 and len(M)==drops:
  for x,y,s in M:
    dx=0
    dy=1
    if s==3: dy=2
    elif s==2: dx=1
    print x+dx,y+dy,s

#start_time = time.clock() 

#print time.clock() - start_time, "seconds"

Submission status: Accepted

Solution code:
def read_data():
  n=input()
  x=[]
  for i in range(10):
    x.append(map(int,raw_input().split()))
  return n, x

def is_area3(x,y):
  if x>7 or y>5: return False
  for dx in [0,1,2,1,0]:
    A = P[y][x-dx:x+dx+1]
    if A.count(0)>0: return False
    y += 1
  return True
      
def is_area2(x,y):
  if x>7 or y>7: return False
  for dy in [0,1,2]:
    A = P[y+dy][x:x+3]
    if A.count(0)>0: return False
  return True

def is_area1(x,y):
  if x>8 or y>7: return False
  for dx in [0, 1, 0]:
    A = P[y][x-dx:x+dx+1]
    if A.count(0)>0: return False
    y += 1
  return True

def ink(x,y,s,m):
  global P
  for dy,dx in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
    P[y+dy][x+dx]+=m
  if s==1: return
  for dy,dx in [[1,1],[1,-1],[-1,1],[-1,-1]]:
    P[y+dy][x+dx]+=m
  if s==2: return
  for dy,dx in [[2,0],[-2,0],[0,2],[0,-2]]:
    P[y+dy][x+dx]+=m
  return

drops, P = read_data()
M=[]
i=-1
step =3
while i<99:
  i+=1
  y = i / 10
  x = i % 10
  if P[y][x]==0: continue

  if step==3:
    while is_area3(x,y):
      M.append([x,y,3])
      ink(x,y+2,3,-1)
    if P[y][x]==0:
      step = 3
      continue
    else: step = 2

  if step==2:
    while is_area2(x,y):
      M.append([x,y,2])
      ink(x+1,y+1,2,-1)
    if P[y][x]==0:
      step = 3
      continue
    else: step = 1

  if step==1:
    while is_area1(x,y):
      M.append([x,y,1])
      ink(x,y+1,1,-1)
    if P[y][x]==0:
      step = 3
      continue
    else: step = 0

  dx=0
  dy=1
  if step==0 and len(M)>0:
    x,y,tmp = M.pop()
    if tmp==3: dy=2
    elif tmp==2: dx=1
    ink(x+dx,y+dy,tmp,1)
    i = y*10+x-1
    step = tmp-1
  else: break
if drops <=12 and len(M)==drops:
  for x,y,s in M:
    dx=0
    dy=1
    if s==3: dy=2
    elif s==2: dx=1
    print x+dx,y+dy,s

Submission status: Accepted

Solution code:
def read_data():
  n=input()
  x=[]
  for i in range(10):
    x.append(map(int,raw_input().split()))
  return n, x
 
def is_area3(x,y):
  if x>7 or y>5: return False
  for dx in [0,1,2,1,0]:
    A = P[y][x-dx:x+dx+1]
    if A.count(0)>0: return False
    y += 1
  return True
       
def is_area2(x,y):
  if x>7 or y>7: return False
  for dy in [0,1,2]:
    A = P[y+dy][x:x+3]
    if A.count(0)>0: return False
  return True
 
def is_area1(x,y):
  if x>8 or y>7: return False
  for dx in [0, 1, 0]:
    A = P[y][x-dx:x+dx+1]
    if A.count(0)>0: return False
    y += 1
  return True
 
def ink(x,y,s,m):
  global P
  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]
  for i in range([5,9,13][s-1]):
    P[y+dy[i]][x+dx[i]]+=m
  return
 
drops, P = read_data()
M=[]
i=-1
step =3
while i<99:
  i+=1
  y = i / 10
  x = i % 10
  if P[y][x]==0: continue
 
  if step==3:
    while is_area3(x,y):
      M.append([x,y,3])
      ink(x,y+2,3,-1)
    if P[y][x]==0:
      step = 3
      continue
    else: step = 2
 
  if step==2:
    while is_area2(x,y):
      M.append([x,y,2])
      ink(x+1,y+1,2,-1)
    if P[y][x]==0:
      step = 3
      continue
    else: step = 1
 
  if step==1:
    while is_area1(x,y):
      M.append([x,y,1])
      ink(x,y+1,1,-1)
    if P[y][x]==0:
      step = 3
      continue
    else: step = 0
 
  dx=0
  dy=1
  if step==0 and len(M)>0:
    x,y,tmp = M.pop()
    if tmp==3: dy=2
    elif tmp==2: dx=1
    ink(x+dx,y+dy,tmp,1)
    i = y*10+x-1
    step = tmp-1
  else: break
if drops <=12 and len(M)==drops:
  for x,y,s in M:
    dx=0
    dy=1
    if s==3: dy=2
    elif s==2: dx=1
    print x+dx,y+dy,s

Submission status: Accepted

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,sp):
    if len(drops)==0:
        return []
    for i in range(sp,100):
        if C[i/10][i%10]>0:
            break
        sp+=1
    for size in set(drops):
        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.remove(size)
                    ans=findAns(C,drops,sp)
                    if ans!=False:
                        ans.append([sx,sy,size])
                        return ans
                    drops.append(size)
                    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=[list(a) for a in itertools.combinations_with_replacement([0,13,9,5],n) if sum(a)==sm]
for drops in dropList:
    ans=findAns(C,drops,0)
    if ans!=False:
        break
for a in ans:
    print a[0],a[1],ref[a[2]]
exit()

Submission status: Accepted

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]
        mir = int(d == 2)
        mar = 9 - mir
        for i in range(dn):
            x, y = pointer % 10 + dx[i], pointer // 10 + dy[i]
            if not mir < x < mar or not mir < y < mar:
                continue
            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, pointer)
                    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: Accepted

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]
        for i in range(size):
            if not fab[y + dy[i] + 2][x + dx[i] + 2]:
                break
        else:
            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, xy, 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: Accepted

Solution code:
B,M,S = 13,9,5
dx = [ 0, 0, 1, 0,-1, 1, 1,-1,-1, 0, 2, 0,-2]
dy = [ 0,-1, 0, 1, 0,-1, 1, 1,-1, 2, 0,-2, 0]
def isOnCloth(x,y):
    return 0<=x<10 and 0<=y<10
def soak(cloth,x,y,ink):
    for i in xrange(ink):
        cloth[y+dy[i]][x+dx[i]] -= 1
def drop(cloth,x,y,ink):
    for i in xrange(ink):
        cloth[y+dy[i]][x+dx[i]] += 1
def canSoak(cloth,x,y,ink):
    return all([isOnCloth(x+dx[i],y+dy[i]) and cloth[y+dy[i]][x+dx[i]]>0 for i in xrange(ink)])
def DFS(cloth,ink_set,cur):
    if len(ink_set)==0:
        #print "SUCCESS!"
        return []
    #print "\n".join(map(str,cloth))
    for i in xrange(cur,100):
        #print i
        if not cloth[i/10][i%10] == 0:
            break
        cur += 1
    for ink in set(ink_set):
        #print ink,cur
        for i in xrange(ink):
            cx,cy = cur%10+dx[i],cur/10+dy[i]
            if isOnCloth(cx,cy) and cloth[cy][cx]>0:
                #print cx,cy
                if canSoak(cloth,cx,cy,ink):
                    soak(cloth,cx,cy,ink)
                    ink_set.remove(ink)
                    result = DFS(cloth,ink_set,cur)
                    if not result == False:
                        result.append([cx,cy,ink])
                        return result
                    ink_set.append(ink)
                    drop(cloth,cx,cy,ink)
    return False
ink_set = [B,S]
clothA = [[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],
         [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,0,0,0,0,0],
         [0,0,0,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],
         [0,0,0,0,0,0,0,0,0,0],]
clothB = [[0,0,0,0,0,0,0,0,0,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,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,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0],]
import itertools
n = input()
cloth = []
for u in xrange(10):
    cloth.append(map(int,raw_input().split(" ")))
#print "\n".join(map(str,cloth))
#print 
su = sum([sum(cloth[i]) for i in xrange(10)])
ink_sets = [list(a) for a in itertools.combinations_with_replacement([0,13,9,5],n) if sum(a) == su]
#print ink_sets
for ink_set in ink_sets:
    pass
    result = DFS(cloth,ink_set,0)
    if not result == False:
        break
dic = {B:3,M:2,S:1}
for r in result:
    print "{} {} {}".format(r[0],r[1],dic[r[2]])

Submission status: Accepted

Solution code:
B,M,S = 13,9,5
dx = [ 0, 0, 1, 0,-1, 1, 1,-1,-1, 0, 2, 0,-2]
dy = [ 0,-1, 0, 1, 0,-1, 1, 1,-1, 2, 0,-2, 0]
def isOnCloth(x,y):
    return 0<=x<10 and 0<=y<10
def soak(cloth,x,y,ink):
    for i in xrange(ink):
        cloth[y+dy[i]][x+dx[i]] -= 1
def drop(cloth,x,y,ink):
    for i in xrange(ink):
        cloth[y+dy[i]][x+dx[i]] += 1
def canSoak(cloth,x,y,ink):
    return all([isOnCloth(x+dx[i],y+dy[i]) and cloth[y+dy[i]][x+dx[i]]>0 for i in xrange(ink)])
def DFS(cloth,ink_set,cur):
    if len(ink_set)==0:
        return []
    for i in xrange(cur,100):
        if not cloth[i/10][i%10] == 0:
            break
        cur += 1
    for ink in set(ink_set):
        for i in xrange(ink):
            cx,cy = cur%10+dx[i],cur/10+dy[i]
            if isOnCloth(cx,cy) and cloth[cy][cx]>0:
                if canSoak(cloth,cx,cy,ink):
                    soak(cloth,cx,cy,ink)
                    ink_set.remove(ink)
                    result = DFS(cloth,ink_set,cur)
                    if not result == False:
                        result.append([cx,cy,ink])
                        return result
                    ink_set.append(ink)
                    drop(cloth,cx,cy,ink)
    return False
ink_set = [B,S]
clothA = [[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],
         [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,0,0,0,0,0],
         [0,0,0,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],
         [0,0,0,0,0,0,0,0,0,0],]
clothB = [[0,0,0,0,0,0,0,0,0,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,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,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0],]
import itertools
n = input()
cloth = []
for u in xrange(10):
    cloth.append(map(int,raw_input().split(" ")))
su = sum([sum(cloth[i]) for i in xrange(10)])
ink_sets = [list(a) for a in itertools.combinations_with_replacement([0,13,9,5],n) if sum(a) == su]
for ink_set in ink_sets:
    pass
    result = DFS(cloth,ink_set,0)
    if not result == False:
        break
dic = {B:3,M:2,S:1}
for r in result:
    print "{} {} {}".format(r[0],r[1],dic[r[2]])

Submission status: Accepted

Solution code:
B,M,S = 13,9,5
dx = [ 0, 0, 1, 0,-1, 1, 1,-1,-1, 0, 2, 0,-2]
dy = [ 0,-1, 0, 1, 0,-1, 1, 1,-1, 2, 0,-2, 0]
def isOnCloth(x,y):
    return 0<=x<10 and 0<=y<10
def soak(cloth,x,y,ink):
    for i in xrange(ink):
        cloth[y+dy[i]][x+dx[i]] -= 1
def drop(cloth,x,y,ink):
    for i in xrange(ink):
        cloth[y+dy[i]][x+dx[i]] += 1
def canSoak(cloth,x,y,ink):
    return all([isOnCloth(x+dx[i],y+dy[i]) and cloth[y+dy[i]][x+dx[i]]>0 for i in xrange(ink)])
def DFS(cloth,ink_set,cur):
    if len(ink_set)==0:
        return []
    for i in xrange(cur,100):
        if not cloth[i/10][i%10] == 0:
            break
        cur += 1
    for ink in set(ink_set):
        for i in xrange(ink):
            cx,cy = cur%10+dx[i],cur/10+dy[i]
            if isOnCloth(cx,cy) and cloth[cy][cx]>0:
                if canSoak(cloth,cx,cy,ink):
                    soak(cloth,cx,cy,ink)
                    ink_set.remove(ink)
                    result = DFS(cloth,ink_set,cur)
                    if not result == False:
                        result.append([cx,cy,ink])
                        return result
                    ink_set.append(ink)
                    drop(cloth,cx,cy,ink)
    return False
import itertools
n = input()
cloth = []
for u in xrange(10):
    cloth.append(map(int,raw_input().split(" ")))
su = sum([sum(cloth[i]) for i in xrange(10)])
ink_sets = [list(a) for a in itertools.combinations_with_replacement([0,13,9,5],n) if sum(a) == su]
for ink_set in ink_sets:
    pass
    result = DFS(cloth,ink_set,0)
    if not result == False:
        break
dic = {B:3,M:2,S:1}
for r in result:
    print "{} {} {}".format(r[0],r[1],dic[r[2]])