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: 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]]

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    L = 10
    N = int(readline())
    MP = [list(map(int, readline().split())) for i in range(L)]
    P = []
    for i in range(L):
        for j in range(L):
            if MP[i][j]:
                P.append((j, i))
    A = [(0, 0), (-1, 1), (0, 1), (1, 1), (0, 2)]
    B = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
    C = [(0, 0), (-1, 1), (0, 1), (1, 1), (-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 3), (0, 3), (1, 3), (0, 4)]
    ans = []
    K = len(P)
    def dfs(i, k):
        if i == K:
            return (k == N)
        x, y = P[i]
        if MP[y][x] == 0:
            if dfs(i+1, k):
                return 1
        if 0 < x < L-1 and y < L-2 and all(MP[y+q][x+p] for p, q in A):
            for p, q in A:
                MP[y+q][x+p] -= 1
            if dfs(i, k+1):
                ans.append((x, y+1, 1))
                return 1
            for p, q in A:
                MP[y+q][x+p] += 1
        if x < L-2 and y < L-2 and all(MP[y+q][x+p] for p, q in B):
            for p, q in B:
                MP[y+q][x+p] -= 1
            if dfs(i, k+1):
                ans.append((x+1, y+1, 2))
                return 1
            for p, q in B:
                MP[y+q][x+p] += 1
        if 1 < x < L-2 and y < L-4 and all(MP[y+q][x+p] for p, q in C):
            for p, q in C:
                MP[y+q][x+p] -= 1
            if dfs(i, k+1):
                ans.append((x, y+2, 3))
                return 1
            for p, q in C:
                MP[y+q][x+p] += 1
    dfs(0, 0)
    for x, y, t in ans:
        write("%d %d %d\n" % (x, y, t))
solve()

Submission status: Runtime Error

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>8 or y>6: 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>8: 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
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: Runtime Error

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>8 or y>6: 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>8: 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 len(M)<=12:
  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: Runtime Error

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>8 or y>6: 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>8: 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 len(M)<=12:
  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: Runtime Error

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():
  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>8 or y>6: 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>8: 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 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: Runtime Error

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():
  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>8 or y>6: 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>8: 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: Runtime Error

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>6: 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>8: 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: Runtime Error

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()
A=[]
i=-1
m=3
while i<99:
  i+=1
  y=i/10
  x=i%10
  if P[y][x]==0: continue

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

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

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

  dx=[0,1,0]
  dy=[1,1,2]
  if m==0 and len(A)>0:
    x,y,m=A.pop()
    m-=1
    ink(x+dx[m],y+dy[m],m+1,1)
    i = y*10+x-1
  else: break

if drops <=12 and len(A)==drops:
  for x,y,s in A: print x+dx[s-1],y+dy[s-1],s

Submission status: Runtime Error

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()
A=[]
i=-1
m=3
while i<99:
  i+=1
  y=i/10
  x=i%10
  if P[y][x]==0: continue

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

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

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

  dx=[0,1,0]
  dy=[1,1,2]
  if m==0 and len(A)>0:
    x,y,m=A.pop()
    m-=1
    ink(x+dx[m],y+dy[m],m+1,1)
    i = y*10+x-1
  else:
    break
if drops <=12 and len(A)==drops:
  for x,y,s in A: print x+dx[s-1],y+dy[s-1],s

Submission status: Runtime Error

Solution code:
import sys
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()
A=[]
i=-1
m=3
while i<99:
  i+=1
  y=i/10
  x=i%10
  if P[y][x]==0: continue

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

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

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

  dx=[0,1,0]
  dy=[1,1,2]
  if m==0 and len(A)>0:
    x,y,m=A.pop()
    m-=1
    ink(x+dx[m],y+dy[m],m+1,1)
    i = y*10+x-1
  else:
    break
if drops <=12 and len(A)==drops:
  for x,y,s in A: print x+dx[s-1],y+dy[s-1],s

Submission status: Runtime Error

Solution code:
import sys

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()
A=[]
i=-1
m=3
while i<99:
  i+=1
  y=i/10
  x=i%10
  if P[y][x]==0: continue

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

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

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

  dx=[0,1,0]
  dy=[1,1,2]
  if m==0 and len(A)>0:
    x,y,m=A.pop()
    m-=1
    ink(x+dx[m],y+dy[m],m+1,1)
    i = y*10+x-1
  else:
    break

if drops <=12 and len(A)==drops:
  for x,y,s in A: print x+dx[s-1],y+dy[s-1],s

Submission status: Runtime Error

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[y + dy][x + dx]:
            cloth[y + dy][x + dx] -= 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: 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

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 find(cloth, drops, history):
    for d in range(2, -1, -1):
        if not drops[d]:
            continue
        (start, stop) = (1, 9) if d < 2 else (2, 8)
        for y in range(start, stop):
            for x in range(start, stop):
                for dxy in dxys[d]:
                    (dx, dy) = dxy
                    if not cloth[y + dy][x + dx]:
                        break
                else:
                    new_cloth, new_drops, new_history = [r[:] for r in cloth], drops[:], history[:]
                    for dxy in dxys[d]:
                        (dx, dy) = dxy
                        new_cloth[y + dy][x + dx] -= 1

                    new_drops[d] -= 1
                    new_history.append((x, y, 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