Problem : 48 - 買醬油I

Problem Statistics

Solved Member: 40　　Submission: 132　　User Tried: 43

Statement:

你聽過梓喵買醬油的傳說嗎？如果沒聽過的話沒關係，下面將會告訴你這個神奇的傳說。

傳說中，有個騎腳踏車的雙馬尾女孩叫梓喵，她每天都會出門買醬油(沒辦法，她家開餐廳，醬油用很快)。據說她騎腳踏車非常之快，甚至比蜻蜓還要更快。而被她的腳踏車撞到的人，將會得到一輩子幸福。

某天，你為了驗證這個傳說，你決定也過去給她撞撞看(?)。你拿出了N-1天前記錄她騎腳踏車的路線圖，發現有神祕的規律：

1.梓喵家住在城鎮的(1,1)。
2.梓喵所在的城鎮是長W，寬H的城鎮。城鎮的街道為棋盤狀，任一條直的街道和橫的街道形成一個十字路口。
3.梓喵很喜歡運動，所以會特地跑到其他城鎮的便利商店買醬油，她到的便利商店恰好都是鄰邊城鎮的第一個十字路口。你希望到她會到達的便利商店前被她撞。並且你可以假設旁邊的城鎮處處都有便利商店。
4.梓喵喜歡新鮮感，也就是她不喜歡走跟昨天相同的路線。每到一個十字路口，她會視情況往東或者往南走，並且選擇的方向一定會和上一次經過這個十字路口時的選擇不一樣。

我們可以用下面的圖來簡略表示，右邊為東，下面為南，當中(1,1)到(W,H)為梓喵所住的城鎮，以外為鄰近城鎮：

你現在有了他N-1天前的路線圖，你想知道她今天會到哪一家便利商店買醬油。

Input:Output:

第1行有3個整數，H,W,N，以空格分開。(H <= 1000 , W <= 1000 , N <= 1000000)。
接下來有H行，每行有W個整數，第i行第j個整數代表座標(i,j)的十字路口的情形。0代表當天往南，1代表往東。
30%的測資保證H,W <=100，且 N <= 1000。

輸出只有1行，2個整數，代表她今天會到的便利商店的座標。

Sample Input:Sample Output:

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

1 5

HINT:

這是範測當中，從2天前到今天每天所走的路線圖。

題外話：
1.請勿google跟題目敘述有關係的關鍵字，恕不負責任。
2.附建成盃其實考過，當初這題最初的敘述其實是長這樣，不過被河蟹了。

Source:

JOI 2008/2009 本選

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10