← 返回题目列表

AtCoder · joi2009ho_d

D. 步行

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

散歩 - 原题 PDF 第 1 页
原题PDF第10页
散歩 - 原题 PDF 第 2 页
原题PDF第11页
可复制的 PDF 提取文本
4                       散歩 


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





                (H + 1, 1)                     (H + 1, W + 1)

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

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

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

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

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




                       問題4-1

入力

 入力ファイルのファイル名はinput.txt である.
  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 を
満たす.


出力

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


入出力の例

  例
   input.txt

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


   output.txt

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


東  南  東  東     南  東  東  東     東  東  東  東


南  東  南  南     南  南  東  南     東  南  東  南


東  南  東  南     東  南  南  東     南  東  南  東



                       問題4-2