Problem:


あみだくじ II

縦線が n 本のあみだくじがあります。このあみだくじは以下の条件を満たしています。

横線は真横に引きます。斜めに引くことはありません。

横線は必ず隣り合った縦線同士をつなぎます。つまり、横線が縦線をまたぐことはありません。

どの縦線についても同じ点から左右同時に横線が出ることはありません。つまり、横線が縦線を横切ることはありません。

当りはひとつだけです。

下図 に n = 5 のときの、あみだくじの例を示します。上側の数字は縦線の番号(左から1, 2, 3, 4, 5 ) を表します。☆が当たりです。

縦線の本数 n、選んだ縦線の番号 m、あみだくじの当りの場所、各段における横線の有無を読み込んで、当りにたどり着けるかどうかの判定を出力するプログラムを作成してください。ただし、与えられたあみだくじの任意の位置に1 本だけ横線を付け加えることができるものとします（付け加えなくてもかまいません）。横線を1 本付け加えた後のあみだくじも前述の条件を満たしていなければなりません。

Input

複数のデータセットが与えられます。各データセットは以下のとおりです：

１行目に、縦線の本数 n (1 < n ≤ 10) が書かれています。

２行目には、選んだ縦線の番号 m (1 ≤ m ≤ n) が書かれています。

３行目には、当りの場所（図でいう☆）が左から数えて何番目かが書かれています。

４行目には、あみだくじの段数 d (1 ≤ d ≤ 30) が書かれています。

５行目以降は、図に対応する数字の並びのように、あみだくじの上から順に、各縦線の間に横線があるときを 1、ないときを 0 として、n - 1 つの数字が並んでいます。

入力は１つの 0 が書かれた行で終わります。

Output

各データセットについて、選んだ縦線の番号 m から当りにたどり着けるかどうかに応じて以下の値を出力してください。

横線を引かなくても当りにたどり着けるときは 0 を出力してください。

横線を1 本引けば当りにたどり着けるときは、その中で最も出発側（図でみて上）に近い横線の位置を出力してください。出発側から数えて何段目（図 を参考にしてください）に、左から数えて何番目の縦線から右に向かって横線を引くかを半角の空白で区切って出力してください。

横線を1 本引いても当りにたどり着けないときには 1 を出力してください。

Sample Input

5
2
3
9
1010
1001
0100
1001
0010
1000
0100
0101
1010
0

Output for the Sample Input

6 4



Sample input:
5
2
3
9
1010
1001
0100
1001
0010
1000
0100
0101
1010
0


Sample output:
6 4

Submission status: Wrong Answer

Solution code:
import sys
import itertools


def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)-1):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu


def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

n = input()
m = input()
star = input()
d = input()
lis = range(1,n+1)
lots = []
for i in xrange(d):
    lots.append([ 1 if e == '1' else 0 for e in list(raw_input()) ] )

if solve(lots,lis)[m-1] == star: print 0;exit()
lis = range(1,n+1)
#print one_step(lots,lis)
for i in xrange(d):
    print i,"-->"
    if lots[0][0] == 0 and lots[0][1] == 0:
        lots[0][0] = 1
        if solve(lots,lis)[star-1] == m: print i+1,1;exit()
        lots[0][0] = 0
    if lots[0][n-3] == 0 and lots[0][n-2] == 0:
        lots[0][n-2] = 1
        if solve(lots,lis)[star-1] == m: print i+1,n-1;exit()
        lots[0][n-2] = 0
    for j in xrange(1,n-2):
        if lots[0][j-1] == 0 and lots[0][j] == 0 and lots[0][j+1] == 0:
            lots[0][j] = 1
            if solve(lots,lis)[star-1] == m: print i+1,j+1;exit()
            lots[0][j] = 0
    lots,lis = one_step(lots,lis)
print 1

Submission status: Wrong Answer

Solution code:
import sys
import itertools


def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)-1):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu


def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

n = input()
m = input()
star = input()
d = input()
lis = range(1,n+1)
lots = []
for i in xrange(d):
    lots.append([ 1 if e == '1' else 0 for e in list(raw_input()) ] )

if solve(lots,lis)[m-1] == star: print 0;exit()
lis = range(1,n+1)
#print one_step(lots,lis)
for i in xrange(d):
    if lots[0][0] == 0 and lots[0][1] == 0:
        lots[0][0] = 1
        if solve(lots,lis)[star-1] == m: print i+1,1;exit()
        lots[0][0] = 0
    if lots[0][n-3] == 0 and lots[0][n-2] == 0:
        lots[0][n-2] = 1
        if solve(lots,lis)[star-1] == m: print i+1,n-1;exit()
        lots[0][n-2] = 0
    for j in xrange(1,n-2):
        if lots[0][j-1] == 0 and lots[0][j] == 0 and lots[0][j+1] == 0:
            lots[0][j] = 1
            if solve(lots,lis)[star-1] == m: print i+1,j+1;exit()
            lots[0][j] = 0
    lots,lis = one_step(lots,lis)
print 1

Submission status: Wrong Answer

Solution code:
import sys
import itertools


def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)-1):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu


def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

n = input()
m = input()
star = input()
d = input()
lis = range(1,n+1)
lots = []
for i in xrange(d):
    lots.append([ 1 if e == '1' else 0 for e in list(raw_input()) ] )

if solve(lots,lis)[star-1] == m: print 0;exit()
lis = range(1,n+1)
#print one_step(lots,lis)
for i in xrange(d):
    if lots[0][0] == 0 and lots[0][1] == 0:
        lots[0][0] = 1
        if solve(lots,lis)[star-1] == m: print i+1,1;exit()
        lots[0][0] = 0
    for j in xrange(1,n-2):
        if lots[0][j-1] == 0 and lots[0][j] == 0 and lots[0][j+1] == 0:
            lots[0][j] = 1
            if solve(lots,lis)[star-1] == m: print i+1,j+1;exit()
            lots[0][j] = 0
    if lots[0][n-3] == 0 and lots[0][n-2] == 0:
        lots[0][n-2] = 1
        if solve(lots,lis)[star-1] == m: print i+1,n-1;exit()
        lots[0][n-2] = 0
    lots,lis = one_step(lots,lis)
print 1

Submission status: Wrong Answer

Solution code:
import sys
import itertools


def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)-1):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu


def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

n = input()
m = input()
star = input()
d = input()
lis = range(1,n+1)
lots = []
for i in xrange(d):
    lots.append([ 1 if e == '1' else 0 for e in list(raw_input()) ] )

if solve(lots,lis)[star-1] == m: print 0;exit()
for i in xrange(d):
    if lots[0][0] == 0 and lots[0][1] == 0:
        lots[0][0] = 1
        if solve(lots,lis)[star-1] == m: print i+1,1;exit()
        lots[0][0] = 0
    for j in xrange(1,n-2):
        if lots[0][j-1] == 0 and lots[0][j] == 0 and lots[0][j+1] == 0:
            lots[0][j] = 1
            if solve(lots,lis)[star-1] == m: print i+1,j+1;exit()
            lots[0][j] = 0
    if lots[0][n-3] == 0 and lots[0][n-2] == 0:
        lots[0][n-2] = 1
        if solve(lots,lis)[star-1] == m: print i+1,n-1;exit()
        lots[0][n-2] = 0
    lots,lis = one_step(lots,lis)
print 1

Submission status: Wrong Answer

Solution code:
import sys
import itertools


def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu


def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

n = input()
m = input()
star = input()
d = input()
lis = range(n+1)
lots = []
for i in xrange(d):
    lots.append([0]+[ 1 if e == '1' else 0 for e in list(raw_input()) ] +[0])

if solve(lots,lis)[star] == m: print 0;exit()
for i in xrange(d):
    for j in xrange(1,n):
        if lots[0][j-1] == 0 and lots[0][j] == 0 and lots[0][j+1] == 0:
            lots[0][j] = 1
            if solve(lots,lis)[star] == m: print i+1,j;exit()
            lots[0][j] = 0
    lots,lis = one_step(lots,lis)
print 1

Submission status: Wrong Answer

Solution code:
import sys
import itertools


def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu


def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

n = input()
m = input()
star = input()
d = input()
lis = range(n+1)
lots = []
for i in xrange(d):
    lots.append([0]+[ 1 if e == '1' else 0 for e in list(raw_input()) ] +[0])

if solve(lots,lis)[star] == m: print 0;exit()
for i in xrange(d):
    for j in xrange(1,n):
        if lots[i][j-1] == 0 and lots[i][j] == 0 and lots[i][j+1] == 0:
            lots[i][j] = 1
            if solve(lots,lis)[star] == m: print i+1,j;exit()
            lots[i][j] = 0
print 1

Submission status: Wrong Answer

Solution code:
import sys
import itertools


def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu


def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

n = input()
m = input()
star = input()
d = input()
lis = range(n+1)
lots = []
for i in xrange(d):
    lots.append([0]+[ 1 if e == '1' else 0 for e in list(raw_input()) ] +[0])

if solve(lots,lis)[star] == m: print 0;exit()
for i in xrange(d):
    for j in xrange(1,n):
        if lots[i][j-1] == 0 and lots[i][j] == 0 and lots[i][j+1] == 0:
            lots[i][j] = 1
            if solve(lots,lis)[star] == m: print i+1,j;exit()
            lots[i][j] = 0
print 1;exit()

Submission status: Wrong Answer

Solution code:
import sys
import itertools


def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu


def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)


while True:
    n = input()
    if n == 0: exit()
    m = input()
    star = input()
    d = input()
    lis = range(n+1)
    lots = []
    for i in xrange(d):
        lots.append([0]+[ 1 if e == '1' else 0 for e in list(raw_input()) ] +[0])

    if solve(lots,lis)[star] == m: print 0;exit()
    for i,j in itertools.product(xrange(d),xrange(1,n)):
        if lots[i][j-1] == 0 and lots[i][j] == 0 and lots[i][j+1] == 0:
            lots[i][j] = 1
            if solve(lots,lis)[star] == m: print i+1,j;break
            lots[i][j] = 0
    else:print 1

Submission status: Wrong Answer

Solution code:
import sys
import itertools

def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu

def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

while True:
    n = input()
    if n == 0: exit()
    m = input()
    star = input()
    d = input()
    lis = range(n+1)
    lots = []
    for i in xrange(d):
        lots.append([0]+[ 1 if e == '1' else 0 for e in list(raw_input()) ] +[0])

    if solve(lots,lis)[star] == m: print 0;exit()
    for i,j in itertools.product(xrange(d),xrange(1,n)):
        if lots[i][j-1] == 0 and lots[i][j] == 0 and lots[i][j+1] == 0:
            lots[i][j] = 1
            if solve(lots,lis)[star] == m: print i+1,j;break
            lots[i][j] = 0
    else:print 1

Submission status: Wrong Answer

Solution code:
def check(n,m,star,d,f):
    ns=[i for i in range(n)]
    for i in range(d):
        for j in range(n-1):
            if f[i][j]:
                c=ns[j+1]
                ns[j+1]=ns[j]
                ns[j]=c
    return ns[star-1]==m-1



while True:
    n=int(input())
    if(n==0):break
    m=int(input())
    star=int(input())
    d=int(input())
    f=[[False for i in range(n-1)]for j in range(d)]
    for i in range(d):
        st=input()
        for j in range(n-1):
            f[i][j]=st[j]=='1'
    if check(n,m,star,d,f):
        print(1)
    else:
        ans=False
        for i in range(d):
            for j in range(n-1):
                if ans:break
                ok=not f[i][j]
                if(j>0 and f[i][j-1]) or (j<n-2 and f[i][j+1]):ok=False
                if ok:
                    f[i][j]=True
                    if check(n,m,star,d,f):
                        print(i+1,j+1)
                        ans=True
                    f[i][j]=False
        if not ans:
            print(0)

Submission status: Wrong Answer

Solution code:
def check_lots(start, goal, line):
    for i in range(len(line)):
        for j in range(len(line[i])):
            if line[i][j] == 1:
                if j == start - 1:
                    start -= 1
                elif j == start:
                    start += 1
    return start == goal

while True:
    n = int(input())
    if n == 0:
        break
    m = int(input())
    s = int(input())
    d = int(input())
    l = []
    for i in range(d):
        l.append([0] + list(map(int, list(input()))) + [0])
    d_ans = 0
    n_ans = 0
    if check_lots(m, s, l):
        print(0)
    else:
        for i in range(d):
            for j in range(1, n):
                l_tmp = l[:]
                if sum(l_tmp[i][j-1:j+2]) > 0:
                    continue
                l_tmp[i][j] = 1
                if check_lots(m, s, l_tmp):
                    d_ans = i + 1
                    n_ans = j
                    break
            else:
                continue
            break
        if d_ans:
            print(d_ans, n_ans)
        else:
            print(1)

Submission status: Wrong Answer

Solution code:
while True:
  n = int(input())
  if not n:
    break

  start = int(input()) - 1 #開始の位置
  goal = int(input()) - 1  #あたりの位置
  d = int(input())
  
  nums = [[i for i in range(n)]] #各段での数字の並び
  bars = [] #横棒リスト
  
  for i in range(d):
    s = input()
    bars.append(s)
    new = nums[-1][:]

    for j in range(n - 1):
      if s[j] == "1": #横棒があれば入れ替え
        new[j], new[j + 1] = new[j + 1], new[j]

    nums.append(new)
  
  to_goal = nums[-1][goal] #あたりにたどり着くスタートの番号

  for i, status in enumerate(nums):
    to_goal_ind = status.index(to_goal) #to_goalの位置
    start_ind = status.index(start)     #startの位置
    ind1, ind2 = min(to_goal_ind, start_ind), max(to_goal_ind, start_ind)

    if ind2 - ind1 == 1:  #隣あっていた場合
      if i <= d - 1 and bars[i][ind1] == "0" and (ind2 == n - 1 or bars[i][ind2] == "0"):  #隣り合う横棒がなければ出力
        print(i + 1, ind1 + 1)
        break
  else:
    print(1)

Submission status: Wrong Answer

Solution code:
while True:
  n = int(input())
  if not n:
    break

  start = int(input()) - 1 #開始の位置
  goal = int(input()) - 1  #あたりの位置
  d = int(input())
  
  nums = [[i for i in range(n)]] #各段での数字の並び
  bars = [] #横棒リスト
  
  for i in range(d):
    s = input()
    bars.append(s)
    new = nums[-1][:]

    for j in range(n - 1):
      if s[j] == "1": #横棒があれば入れ替え
        new[j], new[j + 1] = new[j + 1], new[j]

    nums.append(new)
  
  to_goal = nums[-1][goal] #あたりにたどり着くスタートの番号

  for i, status in enumerate(nums[1:]):
    to_goal_ind = status.index(to_goal) #to_goalの位置
    start_ind = status.index(start)     #startの位置
    ind1, ind2 = min(to_goal_ind, start_ind), max(to_goal_ind, start_ind)

    if ind2 - ind1 == 1:  #隣あっていた場合
      if (ind1 == 0 or bars[i][ind1 - 1] == "0") and (ind2 == n - 1 or bars[i][ind2] == "0"):  #隣り合う横棒がなければ出力
        print(i + 1, ind1 + 1)
        break
  else:
    print(1)

Submission status: Wrong Answer

Solution code:
while True:
  n = int(input())
  if not n:
    break

  start = int(input()) - 1 #開始の位置
  goal = int(input()) - 1  #あたりの位置
  d = int(input())
  
  nums = [[i for i in range(n)]] #各段での数字の並び
  bars = [] #横棒リスト
  
  for i in range(d):
    s = input()
    bars.append(s)
    new = nums[-1][:]

    for j in range(n - 1):
      if s[j] == "1": #横棒があれば入れ替え
        new[j], new[j + 1] = new[j + 1], new[j]

    nums.append(new)
  
  to_goal = nums[-1][goal] #あたりにたどり着くスタートの番号

  for i, status in enumerate(nums[1:]):
    to_goal_ind = status.index(to_goal) #to_goalの位置
    start_ind = status.index(start)     #startの位置
#    print(bars[i])
#    print(status)
    ind1, ind2 = min(to_goal_ind, start_ind), max(to_goal_ind, start_ind)

    if ind2 - ind1 == 1:  #隣あっていた場合
      if (bars[i][ind1] == "0") and (ind1 == 0 or bars[i][ind1 - 1] == "0") and (ind2 == n - 1 or bars[i][ind2] == "0"):  #隣り合う横棒がなければ出力
        print(i + 1, ind1 + 1)
        break
  else:
    print(1)

Submission status: Wrong Answer

Solution code:
def Judge(data,n,d,m):
    now=m-1
    for i in range(d):
        if now==0:
            if data[i][now]:
                now+=1
        elif now==n-1:
            if data[i][n-2]:
                now-=1
        elif data[i][now-1]:
            now-=1
        elif data[i][now]:
            now+=1
    return now+1

while True:
    n=input()
    if n==0:break
    m,star,d=input(),input(),input()
    data=[map(int,raw_input()) for i in range(d)]
    flag=False
    if Judge(data,n,d,m)==star:
	print 0
    else:
        for i in range(d):
            for j in range(n-1):
		if data[i][j]==0:
                    data[i][j]=1
                    if Judge(data,n,d,m)==star:
			print i+1,j+1
			flag=True
			break
                    else:
                        data[i][j]=0
            if flag:
		break
	else:
            print 1

Submission status: Wrong Answer

Solution code:
import sys


class Lot:
    def __init__(self, n, w, dan):
        self.n = n
        self.w = w
        self.dan = self._parse_dan(dan)

    def _parse_dan(self, dan):
        dan = map(self._parse_d, dan)
        return dan

    def _parse_d(self, d):
        r = []
        for i in range(len(d)):
            if d[i]:
                r.append((i+1, i+2))
        return r

    def cast(self, m):
        for d in self.dan:
            for b in d:
                if b[0] == m:
                    m = b[1]
                elif b[1] == m:
                    m = b[0]
        if m == self.w:
            return 0
        else:
            return 1



def solv(n, w, dan, m):
    lot = Lot(n, w, dan)
    r = lot.cast(m)
    if r == 0:
        return r
    else:
        a_bars = additional_bar(dan)
        for ab in a_bars:
            dan2 = map(list, dan)
            a, b = ab
            dan2[a][b] = 1
            lot = Lot(n, w, dan2)
            r = lot.cast(m)
            if r == 0:
                return "%d %d" % (a+1, b+1)
        return 1


def additional_bar(dan):
    r = []
    for d in range(len(dan)):
        if dan[d][0:2] == [0,0]:
            r.append((d, 0))
        if dan[d][-2:] == [0,0]:
            r.append((d, len(dan[d])-1))
        for i in range(len(dan[d])-2):
            if dan[d][i:i+3] == [0,0,0]:
                r.append((d, i+1))
    return r



while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit(0)
    m = int(sys.stdin.readline())
    w = int(sys.stdin.readline())
    d = int(sys.stdin.readline())
    dan = []
    for i in range(d):
        dan.append(map(int, list(sys.stdin.readline().rstrip())))
    print solv(n, w, dan, m)

Submission status: Wrong Answer

Solution code:
import sys


class Lot:
    def __init__(self, n, w, dan):
        self.n = n
        self.w = w
        self.dan = self._parse_dan(dan)

    def _parse_dan(self, dan):
        dan = map(self._parse_d, dan)
        return dan

    def _parse_d(self, d):
        r = []
        for i in range(len(d)):
            if d[i]:
                r.append((i+1, i+2))
        return r

    def cast(self, m):
        for d in self.dan:
            for b in d:
                if b[0] == m:
                    m = b[1]
                elif b[1] == m:
                    m = b[0]
        if m == self.w:
            return 0
        else:
            return 1



def solv(n, w, dan, m):
    lot = Lot(n, w, dan)
    r = lot.cast(m)
    if r == 0:
        return r
    else:
        a_bars = additional_bars(dan)
        for ab in a_bars:
            dan2 = map(list, dan)
            a, b = ab
            dan2[a][b] = 1
            lot = Lot(n, w, dan2)
            r = lot.cast(m)
            if r == 0:
                return "%d %d" % (a+1, b+1)
        else:
            return 1


def additional_bars(dan):
    r = []
    for d in range(len(dan)):
        if dan[d][0:2] == [0,0]:
            r.append((d, 0))
        if dan[d][-2:] == [0,0]:
            r.append((d, len(dan[d])-1))
        for i in range(len(dan[d])-2):
            if dan[d][i:i+3] == [0,0,0]:
                r.append((d, i+1))
    return r



while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit(0)
    m = int(sys.stdin.readline())
    w = int(sys.stdin.readline())
    d = int(sys.stdin.readline())
    dan = []
    for i in range(d):
        dan.append(map(int, list(sys.stdin.readline().rstrip())))
    print solv(n, w, dan, m)

Submission status: Wrong Answer

Solution code:

import sys


class Lot:
    def __init__(self, n, w, dan):
        self.n = n
        self.w = w
        self.dan = self._parse_dan(dan)

    def _parse_dan(self, dan):
        dan = map(self._parse_d, dan)
        return dan

    def _parse_d(self, d):
        r = []
        for i in range(len(d)):
            if d[i]:
                r.append((i+1, i+2))
        return r

    def cast(self, m):
        for d in self.dan:
            for b in d:
                if b[0] == m:
                    m = b[1]
                elif b[1] == m:
                    m = b[0]
        if m == self.w:
            return 0
        else:
            return 1



def solv(n, w, dan, m):
    lot = Lot(n, w, dan)
    r = lot.cast(m)
    if r == 0:
        return r
    else:
        a_bars = additional_bars(dan)
        for ab in a_bars:
            dan2 = map(list, dan)
            a, b = ab
            dan2[a][b] = 1
            lot = Lot(n, w, dan2)
            r = lot.cast(m)
            if r == 0:
                return "%d %d" % (a+1, b+1)
        else:
            return 1


def additional_bars(dan):
    r = []
    for d in range(len(dan)):
        if dan[d][0:2] == [0,0]:
            r.append((d, 0))
        if dan[d][-2:] == [0,0]:
            r.append((d, len(dan[d])-1))
        for i in range(len(dan[d])-3):
            if dan[d][i:i+3] == [0,0,0]:
                r.append((d, i+1))
    return r



while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit(0)
    m = int(sys.stdin.readline())
    w = int(sys.stdin.readline())
    d = int(sys.stdin.readline())
    dan = []
    for i in range(d):
        dan.append(map(int, list(sys.stdin.readline().rstrip())))
    print solv(n, w, dan, m)

Submission status: Wrong Answer

Solution code:
import sys


class Lot:
    def __init__(self, n, w, dan):
        self.n = n
        self.w = w
        self.dan = self._parse_dan(dan)

    def _parse_dan(self, dan):
        dan = map(self._parse_d, dan)
        return dan

    def _parse_d(self, d):
        r = []
        for i in range(len(d)):
            if d[i]:
                r.append((i+1, i+2))
        return r

    def cast(self, m):
        for d in self.dan:
            for b in d:
                if b[0] == m:
                    m = b[1]
                elif b[1] == m:
                    m = b[0]
        if m == self.w:
            return 0
        else:
            return 1



def solv(n, w, dan, m):
    lot = Lot(n, w, dan)
    r = lot.cast(m)
    if r == 0:
        return r
    else:
        a_bars = additional_bars(dan)
        print a_bars
        for ab in a_bars:
            dan2 = map(list, dan)
            a, b = ab
            dan2[a][b] = 1
            lot = Lot(n, w, dan2)
            r = lot.cast(m)
            if r == 0:
                return "%d %d" % (a+1, b+1)
        else:
            return 1


def additional_bars(dan):
    r = []
    for d in range(len(dan)):
        if dan[d][0:2] == [0,0]:
            r.append((d, 0))
        if dan[d][-2:] == [0,0]:
            r.append((d, len(dan[d])-1))
        for i in range(len(dan[d])-2):
            if dan[d][i:i+3] == [0,0,0]:
                r.append((d, i+1))
    return r



while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit(0)
    m = int(sys.stdin.readline())
    w = int(sys.stdin.readline())
    d = int(sys.stdin.readline())
    dan = []
    for i in range(d):
        dan.append(map(int, list(sys.stdin.readline().rstrip())))
    print solv(n, w, dan, m)

Submission status: Wrong Answer

Solution code:
import sys


class Lot:
    def __init__(self, n, w, dan):
        self.n = n
        self.w = w
        self.dan = self._parse_dan(dan)

    def _parse_dan(self, dan):
        dan = map(self._parse_d, dan)
        return dan

    def _parse_d(self, d):
        r = []
        for i in range(len(d)):
            if d[i]:
                r.append((i+1, i+2))
        return r

    def cast(self, m):
        for d in self.dan:
            for b in d:
                if b[0] == m:
                    m = b[1]
                elif b[1] == m:
                    m = b[0]
        if m == self.w:
            return 0
        else:
            return 1



def solv(n, w, dan, m):
    lot = Lot(n, w, dan)
    r = lot.cast(m)
    if r == 0:
        return r
    else:
        a_bars = additional_bars(dan)
#        print a_bars
        for ab in a_bars:
            dan2 = map(list, dan)
            a, b = ab
            dan2[a][b] = 1
            lot = Lot(n, w, dan2)
            r = lot.cast(m)
            if r == 0:
                return "%d %d" % (a+1, b+1)
        else:
            return 1


def additional_bars(dan):
    r = []
    for d in range(len(dan)):
        if dan[d][0:2] == [0,0]:
            r.append((d, 0))
        if dan[d][-2:] == [0,0]:
            r.append((d, len(dan[d])-1))
        for i in range(len(dan[d])-2):
            if dan[d][i:i+3] == [0,0,0]:
                r.append((d, i+1))
    return r



while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit(0)
    m = int(sys.stdin.readline())
    w = int(sys.stdin.readline())
    d = int(sys.stdin.readline())
    dan = []
    for i in range(d):
        dan.append(map(int, list(sys.stdin.readline().rstrip())))
    print solv(n, w, dan, m)

Submission status: Wrong Answer

Solution code:
import sys
def amida(A,x):
  for e in A:
    if e[x]==1:x+=1
    elif e[x-1]==1:x-=1
  return x
def f():
  for i in D:
    for j in range(1,n):
      if A[i][j]==0:
        B=[e[:] for e in A]
        B[i][j]=1
        if amida(B,m)==p:
          print i+1,j
          return
  print 1
  return

while 1:
  n=input()
  if n==0:break
  m=input()
  p=input()
  D=range(input())
  A=[[0]+map(int,list(raw_input()))+[0] for i in D]
  if amida(A,m)==p:print 0
  else:f()

Submission status: Wrong Answer

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    m = int(raw_input())-1
    x = int(raw_input())-1
    d = int(raw_input())
    amida = []
    for i in range(d):
        amida.append(map(int, raw_input()))
    rroot = []
    for i in range(d-1,-1,-1):
        if x > 0:
            if amida[i][x-1] == 1:
                x -= 1
        if x < n-1:
            if amida[i][x] == 1:
                x += 1
        rroot.append(x)
    if m == x:
        print 0
    else:
        root = []
        for i in range(d):
            if m > 0:
                if amida[i][m-1] == 1:
                    m -= 1
            if m < n-1:
                if amida[i][m] == 1:
                    m += 1
            root.append(m)
        rroot.reverse()
        for i in range(d):
            if abs(root[i]-rroot[i]) == 1:
                p = min(root[i],rroot[i])
                if sum(amida[i][p-1:p+1]) == 0:
                    print i+1, p+1
                    break
            if i == d-1:
                print 1

Submission status: Wrong Answer

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    m,x,d = int(raw_input())-1,int(raw_input())-1,int(raw_input())
    amida = ["" for i in range(d)]
    for i in range(d):
        amida[i] = "0" + raw_input() + "0"
    rroot = []
    for i in range(d-1,-1,-1):
        if amida[i][x-1] == "1":
            x -= 1
        elif amida[i][x] == "1":
            x += 1
        rroot.append(x)
    if m == x:
        print 0
    else:
        root = []
        for i in range(d):
            if amida[i][m-1] == "1":
                m -= 1
            elif amida[i][m] == "1":
                m += 1
            root.append(m)
        rroot.reverse()
        for i in range(d):
            if abs(root[i]-rroot[i]) == 1:
                p = min(root[i],rroot[i])
                if int(amida[i][p-1]) + int(amida[i][p+1]) == 0:
                    print i+1, p+1
                    break
            if i == d-1:
                print 1

Submission status: Accepted

Solution code:
def solve(pos, a):
    for l in a:
        if l[pos-1]:
            pos -= 1
        elif l[pos]:
            pos += 1
    return pos

while True:
    n = int(input())
    if not n:
        break
    m, atari, d = (int(input()) for _ in [0]*3)
    a = [[0]+list(map(int, input()))+[0] for _ in [0]*d]
    if solve(m, a) == atari:
        print(0)
        continue
    for i, (l, (j, current), r) in ((i, _) for i, l in enumerate(a) for _ in zip(l, enumerate(l[1:], start=1), l[2:])):
        if not (l | current | r):
            a[i][j] = 1
            if solve(m, a) == atari:
                print(i+1, j)
                break
            a[i][j] = 0
    else:
        print(1)

Submission status: Accepted

Solution code:
def solver(n, s, g, amida):
    for a in amida:
        a = list(map(int, list(a)))
        r, l = 0, 0
        if s != 1:
            l = a[s-2]
        if s != n:
            r = a[s-1]

        if r == 1:
            s += 1
        elif l == 1:
            s -= 1

    return True if s == g else False

while True:
    n = int(input())
    if n == 0: break
    s = int(input())
    g = int(input())
    d = int(input())
    amida = [input() for j in range(d)]
    if solver(n, s, g, amida):
        print(0)
    else:
        ans = None
        for i in range(d):
            for j in range(n-1):
                a = amida[i]
                if a[j] == '0':
                    a = a[:j] + '1' + a[j+1:]
                    if '11' in a:
                        continue
                    else:
                        if solver(n, s, g, amida[:i] + [a] + amida[i+1:]):
                            ans = str(i+1) + ' ' + str(j+1)
                            break
            if ans: break
        if ans:
            print(ans)
        else:
            print(1)

Submission status: Accepted

Solution code:
import sys
import itertools

def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu

def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

while True:
    n = input()
    if n == 0: exit()
    m = input()
    star = input()
    d = input()
    lis = range(n+1)
    lots = []
    for i in xrange(d):
        lots.append( [0] + map(int,raw_input()) + [0])
    if solve(lots,lis)[star] == m: print 0;continue
    for i,j in itertools.product(xrange(d),xrange(1,n)):
        if lots[i][j-1] + lots[i][j] + lots[i][j+1] == 0:
            lots[i][j] = 1
            if solve(lots,lis)[star] == m: print i+1,j;break
            lots[i][j] = 0
    else: print 1

Submission status: Accepted

Solution code:
import sys
import itertools

def one_step(lo,lis):
    nu = [ e for e in lis ]
    for j in xrange(len(nu)):
        if lo[0][j] == 1:
            nu[j],nu[j+1] = nu[j+1],nu[j]
    return lo[1:],nu

def solve(lo,lis):
    if len(lo) == 0:
        return lis
    nu = [ e for e in lis]
    lo2,nu2 = one_step(lo,nu)
    return solve(lo2,nu2)

def func(lots,lis,n,m,star,d):
    for i in xrange(d):
        for j in xrange(1,n):
            if lots[0][j-1] + lots[0][j] + lots[0][j+1] == 0:
                lots[0][j] = 1
                if solve(lots,lis)[star] == m: print i+1,j;return True
                lots[0][j] = 0
        lots,lis = one_step(lots,lis)
    return False

while True:
    n = input()
    if n == 0: exit()
    m = input()
    star = input()
    d = input()
    lis = range(n+1)
    lots = []
    for i in xrange(d):
        lots.append( [0] + map(int,raw_input()) + [0])
    if solve(lots,lis)[star] == m: print 0;continue
    elif func(lots,lis,n,m,star,d): continue
    else: print 1