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

Solution code:
import sys
f = sys.stdin


while True:
    n = int(f.readline())
    if n ==0:
        break
    m, star, d = [int(f.readline()) for _ in range(3)]
    lines = [f.readline().strip() for _ in range(d)]
    lots = [None for j in range(d + 1)]
    lots[0] = [i + 1 for i in range(n)]
    for i, line in enumerate(lines):
        lots[i + 1] = lots[i][:]
        for j, c in enumerate(line):
            if c == '1':
                lots[i + 1][j], lots[i + 1][j + 1] = lots[i + 1][j + 1], lots[i + 1][j]
    star = lots[-1][star - 1]
    if m == star:
        print(0)
        continue
    for i, lot in enumerate(lots):
        index_min = min(lot.index(m), lot.index(star))
        index_max = max(lot.index(m), lot.index(star))
        if i and index_max - index_min == 1:
            line = lines[i - 1]
            if (index_min == 0 or line[index_min - 1] == '0') and  line[index_min] == '0' and (index_max == n - 1 or  line[index_max] == '0' ):
                print(i, min(lot.index(m), lot.index(star)) + 1)
                break
        if i == len(lots) - 1:
            print(1)

Submission status: Accepted

Solution code:
while 1:
    n=int(raw_input())
    if n==0:
        break
    m=int(raw_input())
    x=int(raw_input())
    d=int(raw_input())
    D=range(d)
    amida=['' for i in D]
    for i in 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 D:
            if amida[i][m-1]=='1':
                m-=1
            elif amida[i][m]=='1':
                m+=1
            root.append(m)
        rroot.reverse()
        for i in 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
                    break
            if i==d-1:
                print 1

Submission status: Accepted

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(0)
    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(1)

Submission status: Accepted

Solution code:
import copy

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 = copy.deepcopy(l[:])
                if sum(l[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: Accepted

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] #あたりにたどり着く初期位置
  
  if to_goal == start: #元からあたりにたどり着く場合
    print(0)

  else: #各段について、to_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 (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: Accepted

Solution code:
def main():
  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] #あたりにたどり着く初期位置
    
    if to_goal == start: #元からあたりにたどり着く場合
      print(0)
  
    else: #各段について、to_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 (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)

main()

Submission status: Accepted

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] #あたりにたどり着く初期位置
  
  if to_goal == start: #元からあたりにたどり着く場合
    print(0)

  else: #各段について、to_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                               #隣り合っていて、 
          and 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: Accepted

Solution code:
# AOJ 0069: Drawing Lots II
# Python3 2018.6.28 bal4u

while True:
	n = int(input())
	if n == 0: break
	m, p, d = [int(input()) for i in range(3)]
	m -= 1
	p -= 1
	a = [[] for i in range(d+1)]
	for i in range(d): a[i] = list(map(int, input()))
	s = [[0 for j in range(n)] for i in range(d+1)]
	s[d] = [i for i in range(n)]
	for i in range(d-1, -1, -1):
		for j in range(n): s[i][j] = s[i+1][j]
		for j in range(n-1):
			if a[i][j]: s[i][j], s[i][j+1] = s[i][j+1], s[i][j]
	k = s[0][m]
	if k == p:
		print(0)
		continue
	f = False
	for i in range(d):
		for j in range(n-1):
			if ((s[i][j] == k and s[i][j+1] == p) or (s[i][j] == p and s[i][j+1] == k)) \
				and (j == 0 or a[i][j-1] == 0) and a[i][j] == 0 and (j == n-2 or a[i][j+1] == 0):
				print(i+1, j+1)
				f = True
				break
		if f: break
	if not f: print(1)

Submission status: Accepted

Solution code:
while True:
    n=input()
    if n==0:
        break
    m,goal,d=input(),input(),input()
    step=[""]*d
    for i in xrange(d):
        step[i]="0"+raw_input()+"0"
    raw=range(n+2)
    for i in xrange(d):
        for j in xrange(1,n+1):
            if step[i][j]=="1":
                raw[j],raw[j+1]=raw[j+1],raw[j]
    ans=0
    if not raw[goal]==m:
        e=raw[goal]
        raw=range(n+2)
        for i in xrange(d):
            if not ans==0:
                break
            for j in xrange(1,n+1):
                if (raw[j]==m and raw[j+1]==e) or (raw[j]==e and raw[j+1]==m):
                    if step[i][j-1]=="0" and step[i][j]=="0" and step[i][j+1]=="0":
                        ans=(i+1,j)
                        break
                if step[i][j]=="1":
                    raw[j],raw[j+1]=raw[j+1],raw[j]
        if ans==0:
            ans=1
    if ans==0 or ans==1:print ans
    else:print " ".join(map(str,ans))

Submission status: Accepted

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

while True:
    n=input()
    if n==0:break
    m,star,d=input(),input(),input()
    data=[[0]+map(int,raw_input())+[0] 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(1,n):
                if data[i][j]==0 and data[i][j+1]!=1 and data[i][j-1]!=1:
                    data[i][j]=1
                    if Judge(data,n,d,m)==star:
                        print i+1,j
                        flag=True
                        break
                    else:
                        data[i][j]=0
            if flag:
                break
        else:
            print 1

Submission status: Accepted

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

def draw_cross(line, end, pos, left):
    if left:
        if pos < 1 or line[pos-1]:
            return False
        elif pos > 1 and line[pos-2]:
            return False
        elif pos < end and line[pos]:
            return False
        line[pos-1] = 1
        return pos

    if pos >= end or line[pos]:
        return False
    elif pos < end-1 and line[pos+1]:
        return False
    elif pos > 0 and line[pos-1]:
        return False
    line[pos] = 1
    return pos + 1

def run(start, side, add, left):
    end = len(side[0])
    pos = start - 1
    add -= 1
    cross = 0

    for step, line in enumerate(side):
        line = line[:]
        if add == step:
            cross = draw_cross(line, end, pos, left)
            if not cross:
                return (False, False)

        if pos > 0 and line[pos-1]:
            pos -= 1
        elif pos < end and line[pos]:
            pos += 1
    return (cross, pos + 1)

while True:
    n = int(stdin.readline())
    if not n:
        break
    start = int(stdin.readline())
    hit = int(stdin.readline())
    num_step = int(stdin.readline())
    side = []
    for i in range(num_step):
        side.append([int(s) for s in stdin.readline().rstrip()])

    cross, goal = run(start, side, 0, True)
    if goal == hit:
        print(0)
        continue
    for step in range(1, num_step+1):
        cross, goal = run(start, side, step, left=True)
        if goal == hit:
            print(step, cross)
            break
        cross, goal = run(start, side, step, left=False)
        if goal == hit:
            print(step, cross)
            break
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
def amida(A,x):
  for e in A:
    if e[x]:x+=1
    elif e[x-1]:x-=1
  return x
def f():
  for i in D:
    for j in range(1,n):
      if A[i][j-1:j+2]==[0,0,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: Accepted

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-1:j+2]=="000":
        B=[e[:] for e in A]
        B[i]=B[i][:j]+"1"+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"+raw_input()+"0" for i in D]
  if amida(A,m)==p:print 0
  else:f()

Submission status: Accepted

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    m = int(raw_input())
    x = int(raw_input())
    d = 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
                    break
            if i == d-1:
                print 1

Submission status: Accepted

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    m,x,d = int(raw_input()),int(raw_input()),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
                    break
            if i == d-1: print 1

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N = int(readline())
    if N == 0:
        return False
    M = int(readline())
    K = int(readline())
    D = int(readline())
    P = [list(map(int, readline().strip())) + [0] for i in range(D)]
    INF = (10, 0); GL = (-1, 0)
    X = [INF]*N
    X[K-1] = GL
    for i in range(D-1, -1, -1):
        Pi = P[i]
        for j in range(N-1):
            if Pi[j]:
                X[j], X[j+1] = X[j+1], X[j]
            elif 0 == Pi[j-1] == Pi[j+1]:
                if X[j] == GL:
                    X[j+1] = (i, j)
                if X[j+1] == GL:
                    X[j] = (i, j)
    if X[M-1] == GL:
        write("0\n")
    elif X[M-1] == INF:
        write("1\n")
    else:
        x, y = X[M-1]
        write("%d %d\n" % (x+1, y+1))
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
from copy import copy

def change(n,a):
    temp = a[n]
    a[n] = a[n+1]
    a[n+1] = temp
    return a

while(1):
    st = 1
    n = int(input())
    if n == 0:
        break
    elif n == 1:
        st = 0
    m_ = int(input())
    m = m_ -1
    w = int(input())
    d = int(input())
    b = []
    forward = []
    for i in range(d):
        b.append([int(i) for i in list(input())])
    if st == 0:
        print("0")
        continue
    a = [i for i in range(n)]
    for i in range(d):
        for j in range(n-1):
            if b[i][j] == 1:
                a = change(j,a)
        forward.append(copy(a))
    if a[w-1] == m:
        print(0)
    else:
        state = True
        pivot = a[w-1]
        for i in range(d):
            f = forward[i]
            x = f.index(m)
            y = f.index(pivot)
            if y - x == 1:
                if b[i][x] == 0 and (x-1 < 0 or b[i][x-1] == 0) and (x+1 > n-2 or b[i][x+1] == 0):
                    print(i+1,x+1)
                    state = False
                    break
            elif x - y == 1:
                if b[i][y] == 0 and (y-1 < 0 or b[i][y-1] == 0) and (y+1 > n-2 or b[i][y+1] == 0):
                    print(i+1,y+1)
                    state = False
                    break
        if state:
            print(1)

Submission status: Runtime Error

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 bars[i][ind1] == "0" and (ind2 == n - 1 or bars[i][ind2] == "0"):  #隣り合う横棒がなければ出力
        print(i + 1, ind1 + 1)
        break
  else:
    print(1)

Submission status: Runtime Error

Solution code:
# AOJ 0069: Drawing Lots II
# Python3 2018.6.28 bal4u

while True:
	n = int(input())
	if n == 0: break
	m, p, d = [int(input()) for i in range(3)]
	a = [[0 for j in range(10)] for i in range(32)]
	for i in range(1, d+1): a[i] = [0] + list(map(int, input())) + [0]
	s = [[0 for j in range(10)] for i in range(32)]
	for i in range(1, n+1): s[d+1][i] = i
	for i in range(d, 0, -1):
		for j in range(1, n+1): s[i][j] = s[i+1][j]
		for j in range(1, n):
			if a[i][j]: s[i][j], s[i][j+1] = s[i][j+1], s[i][j]
	k = s[1][m]
	if k == p:
		print(0)
		continue
	f = False
	for i in range(1, d+1):
		for j in range(1, n):
			if ((s[i][j] == k and s[i][j+1] == p) or (s[i][j] == p and s[i][j + 1] == k)) \
				and a[i][j-1] == 0 and a[i][j] == 0 and a[i][j+1] == 0:
				print(i, j)
				f = True
				break
		if f: break
	if not f: print(1)

Submission status: Runtime Error

Solution code:
while True:
    n=input()
    if n==0:
        break
    m,goal,d=input(),input(),input()
    step=[""]*d
    for i in xrange(d):
        step[i]=raw_input()
    raw=range(1,n+1)
    for i in xrange(d):
        for j in xrange(n-1):
            if step[i][j]=="1":
                raw[j],raw[j+1]=raw[j+1],raw[j]
    ans=0
    if not raw[goal]==m:
        t=raw[goal]
        raw=range(1,n+1)
        for i in xrange(d):
            if not ans==0:break
            for j in xrange(n-1):
                if (raw[j]==m and raw[j+1]==t) or (raw[j+1]==m and raw[j]==t):
                    if (j-1<0 or step[i][j-1]=="0") and (j+1>=n or step[i][j+1]):
                        ans=(i+2,j+1)
                        break
                if step[i][j]=="1":
                    raw[j],raw[j+1]=raw[j+1],raw[j]
        if ans==0:
            ans=1
    print " ".join(map(str,ans))

Submission status: Runtime Error

Solution code:
while True:
    n=input()
    if n==0:
        break
    m,goal,d=input(),input(),input()
    step=[""]*d
    for i in xrange(d):
        step[i]="0"+raw_input()+"0"
    raw=range(n+2)
    for i in xrange(d):
        for j in xrange(1,n+1):
            if step[i][j]=="1":
                raw[j],raw[j+1]=raw[j+1],raw[j]
    ans=0
    if not raw[goal]==m:
        e=raw[goal]
        raw=range(n+2)
        for i in xrange(d):
            if not ans==0:
                break
            for j in xrange(1,n+1):
                if (raw[j]==m and raw[j+1]==e) or (raw[j]==e and raw[j+1]==m):
                    if step[i][j-1]=="0" and step[i][j]=="0" and step[i][j+1]=="0":
                        ans=(i+1,j)
                        break
                if step[i][j]=="1":
                    raw[j],raw[j+1]=raw[j+1],raw[j]
        if ans==0:
            ans=1
    print " ".join(map(str,ans))

Submission status: Runtime Error

Solution code:
import copy
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 range(d):
    for j in range(1,n):
      if A[i][j]==0:
        B=copy.deepcopy(A)
        B[i][j]=1
        if amida(B,m)==p:
          print i+1,j
          return
  print 1
  return
 
import sys
n=input()
m=input()
p=input()
d=input()
A=[]
for s in sys.stdin:
  if s=="0\n":break
  A+=[[0]+map(int,list(s[:-1]))+[0]]
if amida(A,m)==p: print 0
else:f()

Submission status: Runtime Error

Solution code:
import copy,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 range(d):
    for j in range(1,n):
      if A[i][j]==0:
        B=copy.deepcopy(A)
        B[i][j]=1
        if amida(B,m)==p:
          print i+1,j
          return
  print 1
  return
n=input()
m=input()
p=input()
d=input()
A=[]
for s in sys.stdin:
  if s=="0\n":break
  A+=[[0]+map(int,list(s[:-1]))+[0]]
if amida(A,m)==p: print 0
else:f()

Submission status: Runtime Error

Solution code:
import copy,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 range(d):
    for j in range(1,n+1):
      if A[i][j]==0:
        B=copy.deepcopy(A)
        B[i][j]=1
        if amida(B,m)==p:
          print i+1,j
          return
  print 1
  return

n=input()
m=input()
p=input()
d=input()
A=[]
for s in sys.stdin:
  if s=="0\n":break
  A+=[[0]+map(int,list(s[:-1]))+[0]]
if amida(A,m)==p: print 0
else:f()

Submission status: Runtime Error

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 range(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

n=input()
m=input()
p=input()
d=input()
A=[]
for s in sys.stdin:
  if s=="0\n":break
  A+=[[0]+map(int,list(s[:-1]))+[0]]
if amida(A,m)==p: print 0
else:f()

Submission status: Runtime Error

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 < 4:
            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 < 4:
                if amida[i][m] == 1:
                    m += 1
            root.append(m)
        rroot.reverse()
        for i in range(d):
            k = root[i] - rroot[i]
            if abs(k) == 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: Runtime Error

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 p == 0:
                    if amida[i][p+1] == 0:
                        print i+1, p+1
                        break
                elif p == n-1:
                    if amida[i][p-1] == 0:
                        print i+1, p+1
                        break
                else:
                    if amida[i][p-1] + amida[i][p+1]) == 0:
                        print i+1, p+1
                        break
            if i == d-1:
                print 1

Submission status: Runtime Error

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 p == 0:
                    if amida[i][p+1] == 0:
                        print i+1, p+1
                        break
                elif p == n-1:
                    if amida[i][p-1] == 0:
                        print i+1, p+1
                        break
                else:
                    if amida[i][p-1] + amida[i][p+1] == 0:
                        print i+1, p+1
                        break
            if i == d-1:
                print 1

Submission status: Runtime Error

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 p == 0:
                    if amida[i][p+1] == 0:
                        print i+1, p+1
                        break
                elif p == n-2:
                    if amida[i][p-1] == 0:
                        print i+1, p+1
                        break
                else:
                    if amida[i][p-1] + amida[i][p+1] == 0:
                        print i+1, p+1
                        break
            if i == d-1:
                print 1

Submission status: Runtime Error

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):
        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: Runtime Error

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