← 返回题目列表

AtCoder · njpc2017_d

D. 近乎谜题

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

配点 : 600 点

問題文

您正在玩一款名为 NM Puzzle 的益智游戏。 这个游戏是 一张牌,其中一个整数最多为1 减去 NM 一张卡片,其中一个整数最多为 NM 和N 行 M 它是使用一排板来执行的。在这里,卡片上写的整数没有重复。

这个游戏的目的是 就是将卡片排列成 K 。 当棋盘上的每个方格中恰好放置一张牌时,得分为(每行跌倒次数之和)+(每列跌倒次数之和)。

分数只是 输出一张卡片排列使得 K 。

请注意,如果有多个满足条件的输出,则可以输出任何一个。

这里,跌倒次数定义如下。

C_{ij} 位于板上。 i 行 j 表示放置在列方格中的卡片上写的整数。不过,左上角 1 行 1 栏,右下角 N 行 M 列。

  • 行 i (1 ≦ i ≦ N) 跌倒的次数是多少? 满足 1 ≦ j < j’ ≦ M 和 C_{ij} > C_{ij’} 的集合 这是 (j, j’) 的号码。
  • 列 j (1 ≦ j ≦ M) 跌倒的次数是多少? 满足 1 ≦ i < i’ ≦ N 和 C_{ij} > C_{i’j} 的集合 这是 (i, i’) 的号码。

制約

  • 所有输入均为整数。
  • 1 ≦ N, M ≦ 100
  • 0 ≦ K ≦ NM(M-1)/2 + MN(N-1)/2
  • 分数是 K 总有一种卡片排列可以给出以下内容。

入力

输入是按以下格式从标准输入给出的。

N M K

出力

按照以下格式将符合条件的卡片排列输出到标准输出。

  • C_{ij} 位于板上。 i 行 j 表示放置在列方格中的卡片上写的整数。
  • 整数由一个半角空格分隔。
  • C_{ij} 彼此不同; 必须是1 减去 NM 以内的整数。
  • C_{ij} 如下 输出为 N 行 M 列。
C_{11} C_{12} … C_{1M}
C_{21} C_{22} … C_{2M}
:
C_{N1} C_{N2} … C_{NM}

入力例 1

2 3 5

出力例 1

6 1 4
2 5 3

这样排列时,第一行跌倒次数为2次,第二行跌倒次数为1次,第一列跌倒次数为1次,第二列跌倒次数为0次,第三列跌倒次数为1次,因此得分为5,满足条件。

这是一个输出示例;还有其他满足条件的输出。