T584567 [语言月赛 202503] 蛋挞制作工坊
题目描述
Alice 和 Bob 正在教小朋友们制作蛋挞。制作一个蛋挞需要 $m$ 种材料,编号 $1 \sim m$。一个蛋挞当中,材料 $i$ 需要 $g_i$ 克。
有 $n$ 个小朋友(编号为 $1 \sim n$)想要制作蛋挞,其中第 $i$ 个小朋友准备了 $c_{i,j}$ 克的材料 $j$。所有小朋友都用自己准备的材料制作了**尽可能多**的蛋挞。
现在蛋挞已经被食堂叔叔阿姨送进烤箱,小朋友们要排队领取自己的蛋挞,但是领取顺序成了一个难题。
Alice 提倡勤俭节约,所以她会**指定一种材料**,并让所有小朋友按照这种材料的剩余量从少到多排队,这种材料剩余量少的小朋友排在前面。
Bob 鼓励劳动,所以**在 Alice 指定的材料剩余一样多时**,Bob 会让制作出的蛋挞更多的小朋友排在前面;如果制作出的蛋挞也一样多,那么编号小的小朋友排前面。
你现在并不知道 Alice 指定的材料是材料 $1,2,\ldots,m$ 中的哪个,所以你想知道每一种情况下小朋友们的排队结果。
输入格式
无
输出格式
无
说明/提示
### 样例 1 解释
一共有 $2$ 种材料。制作一个蛋挞需要 $3$ 个 $1$ 号材料,$5$ 个 $2$ 号材料。
- $1$ 号小朋友有 $8$ 个 $1$ 号材料,$14$ 个 $2$ 号材料,可以制作 $2$ 个蛋挞。制作完成后,两种材料分别剩余 $8 - 2 \times 3 = 2, 14 - 2 \times 5 = 4$ 个;
- $2$ 号小朋友有 $4$ 个 $1$ 号材料,$9$ 个 $2$ 号材料,可以制作 $1$ 个蛋挞。制作完成后,两种材料分别剩余 $4 - 1 \times 3 = 1, 9 - 1 \times 5 = 4$ 个;
当 Alice 选择材料为 $1$ 号时,
- $1$ 号小朋友剩余 $2$ 个选定材料,$2$ 号小朋友剩余 $1$ 个选定材料;
- $2$ 号小朋友剩余材料比 $1$ 号少,因此 $2$ 号小朋友排在前面。
当 Alice 选择材料为 $2$ 号时,
- $1$ 号小朋友剩余 $4$ 个选定材料,$2$ 号小朋友剩余 $4$ 个选定材料;
- 二者剩余选定材料一样多,但 $1$ 号小朋友制作的蛋挞数量比 $2$ 号多,因此 $1$ 号小朋友排在前面。
### 数据规模与约定
本题共 $10$ 个测试点。对于 $100\%$ 的数据,$1\le n,m\le 50$,$1\le c_{i,j},g_i\le 10^9$(注:$10^9$ 是十亿)。
| 测试点编号 | $n$ | $m$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $= 1$ | $\leq 50$ | 无 |
| $2, 3$ | $\leq 50$ | $= 1$ | 无 |
| $4, 5$ | $\leq 50$ | $\leq 50$ | 所有 $g_i = 1$ |
| $6$ | $\leq 50$ | $\leq 50$ | 所有 $c_{i, j} = g_j$ |
| $7 \sim 10$ | $\leq 50$ | $\leq 50$ | 无 |