UOJ Logo Universal Online Judge

UOJ

#225. 【UR #15】奥林匹克五子棋

统计

各位观众,各位观众,您现在收看的是第 666 届跳蚤奥运会的比赛现场。在刚刚的跳高比赛中,天才跳高小将“最强跳蚤”靠着“最强跳蚤跳跳跳”和经验丰富的伏特跳蚤国王大战了三天三夜,最后战成 $233:233$ 平。考虑到迟迟不能决出胜者,比赛组委会决定临时更换比赛项目,而被选中的则是在跳蚤大陆流行已久的游戏——五子棋。

五子棋是 Picks 博士发明的一款益智类游戏。为了加大难度,这里的五子棋实则是 “$k$ 子棋”。

游戏规则很简单,游戏双方分别使用黑白两色的棋子,下在 $n \times m$ 的棋盘上,先形成 $k$ 子连成一条直线的一方获胜。即,若己方有连续的 $k$ 个棋子形成方向为上下、左右、左上右下、左下右上四个方向之一的直线,就可以获得胜利。

但没想到的是,“最强跳蚤”和伏特跳蚤国王不仅跳得比谁都高,知识水平也是不相上下。啊我们看到,在第 66 局他们再一次打成了平局……

现在是我们的有奖竞猜环节!大家可以来猜猜下一个平局是怎么产生的呢?最早给出答案的观众可以获得小火车一列哦。

现在,你作为一名观众想参与到竞猜环节中。但首先,你需要构造一个下棋过程使得填满整个棋盘之后也没有连续 $k$ 个同色棋子在这四个方向上排成一条直线。

注意,$n \times m$ 可能为奇数,此时先手会比后手多下一步棋。

输入格式

第一行三个正整数 $n,m,k$,意义如前所述。

输出格式

如果双方不能打成平局,输出 $-1$;

否则输出 $n \times m$ 行,第 $i$ 行两个整数 $x_i, y_i$ 表示第 $i$ 次落子的坐标为第 $x_i$ 行第 $y_i$ 列。黑子先行,所以 $i$ 为奇数时为黑方落子,$i$ 为偶数时白方落子。坐标需满足 $1 \le x_i \le n, 1 \le y_i \le m$。

样例一

input

4 4 3

output

1 2
1 1
1 4
1 3
2 1
2 3
2 2
2 4
3 3
3 2
3 4
3 1
4 1
4 4
4 3
4 2

explanation

样例一的参考输出最终得到的棋盘如下:

1 0 1 0
0 0 1 1
1 1 0 0
0 1 0 1

其中 0 为先手,1 为后手。

样例二

input

2 3 3

output

1 1
2 1
2 2
1 2
1 3
2 3

限制与约定

由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 $4$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

子任务 分值 限制
130$2 \leq n,m \leq 4$
215$\min(n,m) = 1$
315$n,m \ge 2, \min(n,m) \lt k$
440$n,m \ge 2$

在所有数据中,都满足 $1 \leq k \leq 10^9$ 且 $1 \le n,m \le 500$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载