Problem:


 散歩 

問題

 JOI 町に住む太郎君は, ある日,健康増進のために散歩を日課にしようと思い立った.
 太郎君の住む JOI 町には,図のように,東西方向に走る (H + 1) 本の道路と,南北
方向に走る (W + 1) 本の道路が碁盤目状に通っている.太郎君の家はもっとも北西の
交差点にあり,ここから散歩を開始する.

 以降,北から a 番目,西から b 番目の交差点を (a, b) で表す.たとえば,太郎君の家がある交差点は (1, 1) である.

図: JOI 町の図 (H = 3, W = 4 の場合).図の上が北,左が西に対応する.

 太郎君は,散歩のルートが日々違ったほうが面白いと考えたので,(1, 1) から (H, W) までの H &times; W 個の交差点に, 「東」または「南」の文字を書き,次のようなルールに従って毎日散歩を行うことにした.

  文字の書かれた交差点にいる場合,その交差点に書かれている文字が「東」な
  ら「南」に, 「南」なら「東」に文字を書き換え,もともと書かれていた文字の方角にある次の交差点まで進む.

 もっとも東やもっとも南の道路に到達したら散歩を終了する.

 この計画を考えた後,太郎君は,将来の散歩で自分がどのようなルートをたどる
ことになるのかが気になった.太郎君のために,太郎君の N 回目の散歩のルートを
予測するプログラムを作成せよ.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

 1 行目には,3 つの正整数が空白区切りで書かれている.これらは,問題文中の 3 つの数値 H, W, N の値である. H, W, N はそれぞれ, 1 ≤ H ≤ 1000, 1 ≤ W ≤ 1000, 1 ≤ N ≤  10000000 = 107 をみたす. 2 行目から H + 1 行目には,それぞれ W 個の整数が空白区切りで書かれている.これらは,太郎君が最初に交差点に書いた文字の情報を表す. i + 1 行目の j 番目の整数が 0 なら,交差点 (i, j) に書かれた文字が「南」であることを, 1 なら, 交差点 (i, j) に書かれた文字が「東」であることを表す.

 採点用データのうち,配点の 30%分については, H ≤ 100, W ≤ 100, N ≤ 1000 を満たす.

H, W, N がすべて 0 のとき入力の終了を示す. データセットの数は 10 を超えない．

出力

データセットごとに次の形式で出力する.

N 回目の散歩において太郎君が散歩を終了する交差点が (i, j) のとき,i と j をこの順に空白で区切って出力せよ.

入出力の例

入力例

3 4 3
1 0 1 1
0 1 0 0
1 0 1 0
0 0 0

出力例

1 5

上の例では,1 回目から 3 回目の散歩のルートは次の図のようになる.

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0
0 0 0


Sample output:
1 5

Submission status: Wrong Answer

Solution code:
#! /usr/bin/python
# -*- coding: utf-8 -*-

dxy = {True:(0, 1), False:(1, 0)}
SOUTH = True
EAST = False

def main():
    # input
    H, W, N = map(int, raw_input().split())
    data = []
    for x in xrange(N):
        data.append(map(makeBool, raw_input().split()))

    last_point = lastReachPoint(data, H, W, N)
    print(str(last_point[1] + 1) + " " + str(last_point[0] + 1))

def makeBool(string):
    if int(string) == 0:
        return True
    else:
        return False

def lastReachPoint(data, H, W, N):
    for x in xrange(N):
        data, last_point = walk(H, W, data)

    return last_point

def walk(H, W, data):
    now_point = (0, 0)
    while now_point[0] < W and now_point[1] < H:
        now_state = data[now_point[1]][now_point[0]]
        next_point = tuple([sum(x) for x in zip(now_point, dxy[now_state])])

        next_state = not now_state
        data[now_point[1]][now_point[0]]= next_state
        now_point = next_point

    return data, next_point

def test():
    data = [[False, True, False, False],
            [True, False, True, True],
            [False, True, False, True]]
    H = 3
    W = 4
    N = 3

    print(lastReachPoint(data, H, W, N))

if __name__=='__main__':
    # test()
    main()

Submission status: Wrong Answer

Solution code:
#! /usr/bin/python
# -*- coding: utf-8 -*-

dxy = {True:(0, 1), False:(1, 0)}
SOUTH = True
EAST = False

def main():
    # input
    H, W, N = map(int, raw_input().split())
    data = []
    for x in xrange(H):
        data.append(map(makeBool, raw_input().split()))

    last_point = lastReachPoint(data, H, W, N)
    print(str(last_point[1] + 1) + " " + str(last_point[0] + 1))

def makeBool(string):
    if int(string) == 0:
        return True
    else:
        return False

def lastReachPoint(data, H, W, N):
    for x in xrange(N):
        data, last_point = walk(H, W, data)

    return last_point

def walk(H, W, data):
    now_point = (0, 0)
    while now_point[0] < W and now_point[1] < H:
        now_state = data[now_point[1]][now_point[0]]
        next_point = tuple([sum(x) for x in zip(now_point, dxy[now_state])])

        next_state = not now_state
        data[now_point[1]][now_point[0]]= next_state
        now_point = next_point

    return data, next_point

def test():
    data = [[False, True, False, False],
            [True, False, True, True],
            [False, True, False, True]]
    H = 3
    W = 4
    N = 3

    print(lastReachPoint(data, H, W, N))

if __name__=='__main__':
    # test()
    main()

Submission status: Wrong Answer

Solution code:
h, w, n = map(int, raw_input().split())
l = [map(int, raw_input().split()) for i in range(h)]
dp = [[0]*w for i in range(h)]
dp[0][0] = n - 1
for i in range(h-1):
    for j in range(w-1):
        dp[i+1][j] += (dp[i][j] + l[i][j] ^ 1) >> 1
        dp[i][j+1] += (dp[i][j] + l[i][j]) >> 1
dx = dy = 0
while dx < w and dy < h:
    if (dp[dy][dx] + l[dy][dx]) % 2 == 0: dy += 1
    else: dx += 1
print dy + 1, dx + 1

Submission status: Wrong Answer

Solution code:
while 1:
    h, w, n = map(int, raw_input().split())
    if h == 0: break
    l = [map(int, raw_input().split()) for i in range(h)]
    dp = [[0]*w for i in range(h)]
    dp[0][0] = n - 1
    for i in range(h-1):
        for j in range(w-1):
            dp[i+1][j] += (dp[i][j] + l[i][j] ^ 1) >> 1
            dp[i][j+1] += (dp[i][j] + l[i][j]) >> 1
    dx = dy = 0
    while dx < w and dy < h:
        if (dp[dy][dx] + l[dy][dx]) % 2 == 0: dy += 1
        else: dx += 1
    print dy + 1, dx + 1

Submission status: Wrong Answer

Solution code:
while 1:
    h, w, n = map(int, raw_input().split())
    if h == 0: break
    l = [map(int, raw_input().split()) for i in range(h)]
    dp = [[0]*w for i in range(h)]
    dp[0][0] = n - 1
    for i in range(h):
        for j in range(w):
            if i + 1 < h: dp[i+1][j] += (dp[i][j] + l[i][j] ^ 1) >> 1
            if j + 1 < w: dp[i][j+1] += (dp[i][j] + l[i][j]) >> 1
    dx = dy = 0
    while dx < w and dy < h:
        if (dp[dy][dx] + l[dy][dx]) % 2 == 0: dy += 1
        else: dx += 1
    print dy + 1, dx + 1

Submission status: Time Limit Exceeded

Solution code:
while True:
  h,w,n = map(int,input().split())
  if not h: break
  sss = [[True if s == "1" else False for s in input().split()] for i in range(h)]
  for i in range(n):
    x = y = 0
    while x < h and y < w:
      sss[x][y] = not sss[x][y]
      if sss[x][y]:
        x += 1
      else:
        y += 1
  print(x + 1,y + 1)

Submission status: Accepted

Solution code:
while 1:
    h, w, n = map(int, raw_input().split())
    if h == 0: break
    l = [map(int, raw_input().split()) for i in range(h)]
    dp = [[0]*w for i in range(h)]
    dp[0][0] = n - 1
    for i in range(h):
        for j in range(w):
            if i + 1 < h: dp[i+1][j] += (dp[i][j] + (l[i][j] ^ 1)) >> 1
            if j + 1 < w: dp[i][j+1] += (dp[i][j] + l[i][j]) >> 1
    dx = dy = 0
    while dx < w and dy < h:
        if (dp[dy][dx] + l[dy][dx]) % 2 == 0: dy += 1
        else: dx += 1
    print dy + 1, dx + 1

Submission status: Accepted

Solution code:
while True:
    h,w,n = map(int, input().split())
    if h==0: break
    
    mapp = []
    for i in range(h):
        hoge = list(map(int,input().split()))
        hoge.append(0)
        mapp.append(hoge)
    mapp.append([0]*(w+1))

    n -= 1
    nmap = [[0]*(w+1) for _ in range(h+1)]
    nmap[0][0] = n
    for i in range(h):
        for j in range(w):
            nmap[i+1][j] += (nmap[i][j]+1-mapp[i][j]) // 2
            nmap[i][j+1] += (nmap[i][j]+mapp[i][j]) // 2
            mapp[i][j] = (nmap[i][j]+mapp[i][j]) % 2

    i,j = 0,0
    while i < h and j < w:
        if mapp[i][j] == 0:
            i += 1
        else:
            j += 1
    print(i+1,j+1)

Submission status: Accepted

Solution code:
while True:
  h,w,n = map(int,input().split())
  if not h: break
  sss = [[1 if s == "1" else 0 for s in input().split()] for i in range(h)]
  dp = [[0 for i in range(w + 1)] for j in range(h + 1)]
  dp[0][0] = n - 1
  for x in range(h):
    for y in range(w):
      a = dp[x][y]
      if sss[x][y]:
        if a % 2:
          dp[x + 1][y] += a // 2
          dp[x][y + 1] += a // 2 + 1
        else:
          dp[x + 1][y] += a // 2
          dp[x][y + 1] += a // 2
      else:
        if a % 2:
          dp[x + 1][y] += a // 2 + 1
          dp[x][y + 1] += a // 2
        else:
          dp[x + 1][y] += a // 2
          dp[x][y + 1] += a // 2
      sss[x][y] = (sss[x][y] + dp[x][y]) % 2

#  print(sss)
#  print(dp)
  x = y = 0
  while x < h and y < w:
    if sss[x][y]:
      y += 1
    else:
      x += 1
  print(x + 1,y + 1)

Submission status: Accepted

Solution code:
def solve():
  while True:
    h,w,n = map(int,input().split())
    if not h: break
    sss = [[1 if s == "1" else 0 for s in input().split()] for i in range(h)]
    dp = [[0 for i in range(w + 1)] for j in range(h + 1)]
    dp[0][0] = n - 1
    for x in range(h):
      for y in range(w):
        a = dp[x][y]
        if sss[x][y]:
          if a % 2:
            dp[x + 1][y] += a // 2
            dp[x][y + 1] += a // 2 + 1
          else:
            dp[x + 1][y] += a // 2
            dp[x][y + 1] += a // 2
        else:
          if a % 2:
            dp[x + 1][y] += a // 2 + 1
            dp[x][y + 1] += a // 2
          else:
            dp[x + 1][y] += a // 2
            dp[x][y + 1] += a // 2
        sss[x][y] = (sss[x][y] + dp[x][y]) % 2
  
  #  print(sss)
  #  print(dp)
    x = y = 0
    while x < h and y < w:
      if sss[x][y]:
        y += 1
      else:
        x += 1
    print(x + 1,y + 1)
  #  print(sss)
solve()

Submission status: Accepted

Solution code:
def solve():
  while True:
    h,w,n = map(int,input().split())
    if not h: break
    sss = [[1 if s == "1" else 0 for s in input().split()] for i in range(h)]
    dp = [[0 for i in range(w + 1)] for j in range(h + 1)]
    dp[0][0] = n - 1
    for x in range(h):
      for y in range(w):
        a = dp[x][y]
        b = sss[x][y]
        if b:
          if a % 2:
            dp[x + 1][y] += a // 2
            dp[x][y + 1] += a // 2 + 1
          else:
            dp[x + 1][y] += a // 2
            dp[x][y + 1] += a // 2
        else:
          if a % 2:
            dp[x + 1][y] += a // 2 + 1
            dp[x][y + 1] += a // 2
          else:
            dp[x + 1][y] += a // 2
            dp[x][y + 1] += a // 2
        sss[x][y] = (a + b) % 2
  
  #  print(sss)
  #  print(dp)
    x = y = 0
    while x < h and y < w:
      if sss[x][y]:
        y += 1
      else:
        x += 1
    print(x + 1,y + 1)
  #  print(sss)
solve()

Submission status: Accepted

Solution code:
def solve():
  while True:
    h,w,n = map(int,input().split())
    if not h: break
    mp = [[int(s) for s in input().split()] for i in range(h)]
    dp = [[0 for i in range(w + 1)] for j in range(h + 1)]
    dp[0][0] = n - 1
    for x in range(h):
      dpx = dp[x]
      dpxp = dp[x + 1]
      mpx = mp[x]
      for y in range(w):
        a = dpx[y]
        b = mpx[y]
        if b:
          if a % 2:
            dpxp[y] += a // 2
            dpx[y + 1] += a // 2 + 1
          else:
            dpxp[y] += a // 2
            dpx[y + 1] += a // 2
        else:
          if a % 2:
            dpxp[y] += a // 2 + 1
            dpx[y + 1] += a // 2
          else:
            dpxp[y] += a // 2
            dpx[y + 1] += a // 2
        mpx[y] = (a + b) % 2
  
    x = y = 0
    while x < h and y < w:
      if mp[x][y]:
        y += 1
      else:
        x += 1
    print(x + 1,y + 1)
solve()

Submission status: Accepted

Solution code:
def main():
    while True:
        import sys
        input=sys.stdin.readline
        h,w,n=map(int,input().split())
        if h==0:
            break
        grid=[list(map(int,input().split())) for _ in [0]*h]
        dp=[[0]*(w+1) for _ in [0]*(h+1)]
        dp[0][0]=n-1
        for k in range(h+w-1):
            for i in range(max(0,k-w+1),min(h,k+1)):
                j=k-i
                x=dp[i][j]
                if grid[i][j]==1:
                    dp[i+1][j]+=x//2
                    dp[i][j+1]+=x-x//2
                else:
                    dp[i][j+1]+=x//2
                    dp[i+1][j]+=x-x//2
        for i in range(h):
            for j in range(w):
                dp[i][j]=(grid[i][j]+dp[i][j])%2
        i,j=1,1
        while True:
            if dp[i-1][j-1]==1:
                j+=1
            else:
                i+=1
            if i>h or j>w:
                break
        print(i,j)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

while True:

    H, W, N = MAP()
    if H == W == H == 0:
        break

    grid = list2d(H, W, 0)
    for i in range(H):
        row = LIST()
        for j in range(W):
            grid[i][j] = row[j]

    # dp[i][j] := (i, j)のマスをN回目の前までに何回通るか
    dp = list2d(H+1, W+1, 0)
    dp[0][0] = N - 1
    for i in range(H):
        for j in range(W):
            # 通る回数が偶数なら半分ずつ
            if dp[i][j] % 2 == 0:
                dp[i+1][j] += dp[i][j] // 2
                dp[i][j+1] += dp[i][j] // 2
            else:
                # 通る回数が奇数なら、元のグリッドの状態に応じて1回多く行く方が決まる
                if grid[i][j] == 0:
                    dp[i+1][j] += dp[i][j] // 2 + 1
                    dp[i][j+1] += dp[i][j] // 2
                else:
                    dp[i+1][j] += dp[i][j] // 2
                    dp[i][j+1] += dp[i][j] // 2 + 1

    # N-1回終了時の状態にグリッドを更新
    for i in range(H):
        for j in range(W):
            grid[i][j] ^= dp[i][j]
            grid[i][j] &= 1

    # N回目の散歩をシミュレーション
    i = j = 0
    while i < H and j < W:
        if grid[i][j] == 0:
            i += 1
        else:
            j += 1
    print(i+1, j+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, takewhile


def read(
    f, *shape, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        return f("".join(takewhile(lambda c: c not in whitespaces, it)).strip())

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[fill_value]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def debug(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    while True:
        h, w, n = map(int, sys.stdin.readline().split())
        if (h, w, n) == (0, 0, 0):
            return
        grid = []
        for _ in range(h):
            row = list(map(int, sys.stdin.readline().split()))
            grid.append(row)

        dp = arr(h, w)
        dp[0][0] = n - 1

        for i in range(h):
            for j in range(w):
                if i < h - 1 and grid[i][j] == 0:
                    dp[i + 1][j] += (dp[i][j] + 1) // 2
                if i < h - 1 and grid[i][j] == 1:
                    dp[i + 1][j] += dp[i][j] // 2
                if j < w - 1 and grid[i][j] == 0:
                    dp[i][j + 1] += dp[i][j] // 2
                if j < w - 1 and grid[i][j] == 1:
                    dp[i][j + 1] += (dp[i][j] + 1) // 2

        for i in range(h):
            for j in range(w):
                grid[i][j] = (grid[i][j] + dp[i][j]) % 2

        i = 0
        j = 0
        while i < h and j < w:
            if grid[i][j] == 0:
                i += 1
            else:
                j += 1
        print(i + 1, j + 1)


if __name__ == "__main__":
    main()