CF207A3 Beaver's Calculator 1.0

来自 ABBYY 的聪明海狸再次让我们大吃一惊！他开发了一种新的计算设备，称之为“海狸计算器 $1.0$”。这台设备非常特别，计划应用于各种科学问题中。 为了测试它，聪明海狸邀请了 $n$ 位科学家，编号从 $1$ 到 $n$。第 $i$ 位科学家带来了 $k_{i}$ 个用于测试的计算问题，这些问题需要用聪明海狸开发的设备来解决。第 $i$ 位科学家的问题编号从 $1$ 到 $k_{i}$，并且必须按照给定的顺序依次计算，因为每个问题的计算都严重依赖于前一个问题的结果。 每个科学家的每个问题由一个整数 $a_{i,j}$ 描述，其中 $i$（$1 \leq i \leq n$）表示科学家的编号，$j$（$1 \leq j \leq k_{i}$）表示问题的编号，$a_{i,j}$ 表示计算设备解决该问题所需的资源单元数。 由聪明海狸开发的这台计算设备非常独特。它会依次逐个解决问题。在解决完一个问题后，在考虑下一个问题之前，设备会分配或释放资源。 对于计算设备来说，释放资源是最昂贵的操作，比分配资源慢得多。因此，希望设备每解决下一个问题时，所需的资源不少于上一个问题。 现在给定科学家们提供的所有问题的信息，你需要安排这些问题的顺序，使得在最终排列中，相邻的“坏对”数量尽可能少。如果在排列中，前一个问题所需的资源比后一个问题多，则这两个连续的问题称为“坏对”。注意，同一位科学家的问题必须按照原顺序解决。

第一行包含一个整数 $n$，表示科学家的数量。为了减小输入规模，接下来的 $n$ 行每行包含五个整数 $k_{i}$、$a_{i,1}$、$x_{i}$、$y_{i}$、$m_{i}$（$0 \leq a_{i,1} < m_{i} \leq 10^{9}$，$1 \leq x_{i}, y_{i} \leq 10^{9}$），分别表示第 $i$ 位科学家的问题数量、首个问题所需资源以及生成后续 $a_{i,j}$ 的三个参数。对于所有 $2 \leq j \leq k_{i}$，$a_{i,j}$ 按如下公式计算： $$ a_{i,j} = (a_{i,j-1} \times x_{i} + y_{i}) \bmod m_{i} $$

第一行输出一个整数，表示最优排列下“坏对”的数量。 如果所有问题的总数不超过 $200000$，还需输出若干行，每行两个整数，分别表示该问题所需的资源数和提出该问题的科学家编号。科学家编号按输入顺序从 $1$ 到 $n$。

在第一个样例中，$n=2$，$k_{1}=2$，$a_{1,1}=1$，$a_{1,2}=2$，$k_{2}=2$，$a_{2,1}=3$，$a_{2,2}=4$。有两位科学家，每人有两个计算问题。第一位科学家的问题分别需要 $1$ 和 $2$ 单位资源，第二位科学家的问题分别需要 $3$ 和 $4$ 单位资源。所有可能的排列（每个问题仅用所需资源数表示）为：$(1,2,3,4)$，$(1,3,2,4)$，$(3,1,2,4)$，$(1,3,4,2)$，$(3,4,1,2)$，$(3,1,4,2)$。 排列 $(1,3,2,4)$ 有一个“坏对”（$3$ 和 $2$），$(3,1,4,2)$ 有两个“坏对”（$3$ 和 $1$，$4$ 和 $2$），而 $(1,2,3,4)$ 没有“坏对”。 由 ChatGPT 4.1 翻译