← 返回题目列表

Codeforces · 207/A2

A2. 海狸的计算器 1.0

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

ABBYY 智能海狸再次给我们带来惊喜!他开发了一种新的计算设备,他称之为“海狸计算器1.0”。它非常奇特,计划用于解决各种科学问题。

为了测试它,智能海狸邀请了n位科学家,编号从1到n。第 i 位科学家为 ABBYY 的 Smart Beaver 开发的设备带来了 ki 计算问题。第 i 个科学家的问题从 1 到 ki 进行编号,并且必须按照所描述的顺序依次计算,因为计算每个问题很大程度上取决于前一个问题的计算结果。

n位科学家每人的每个问题都由一个整数ai,j描述,其中i(1≤i≤n)是科学家的编号,j(1≤j≤ki)是问题的编号,ai,j是计算设备解决该问题所需的资源单元的数量。

Smart Beaver开发的计算装置很不寻常。它按顺序解决问题,一个接一个。在解决某个问题之后并且在考虑下一个问题之前,计算设备分配或释放资源。

计算设备最昂贵的操作是释放资源,其工作速度比分配资源慢得多。因此,期望计算设备的每个下一个问题都需要不比前一个问题更少的资源。

您将获得有关科学家为测试提供的问题的信息。您需要按照这样的顺序排列这些问题,以使列表中相邻的“坏”问题对的数量尽可能最少。如果第一个执行的问题比后面执行的问题需要更多的资源,我们将将此列表中的两个连续问题称为“坏对”。不要忘记,同一位科学家的问题必须以固定的顺序解决。

输入

第一行包含整数 n — 科学家的数量。为了减少输入的大小,接下来的 n 行中的每一行包含五个整数 ki, ai, 1, xi, yi, mi (0 ≤ ai, 1 < mi ≤ 109, 1 ≤ xi, yi ≤ 109) — 第 i 个科学家的问题数量、第一个问题所需的资源以及生成 ai、j 后续值的三个参数。对于从 2 到 ki(含)的所有 j,应通过公式 ai 计算值 ai, j,j = (ai, j - 1 * xi + yi) mod mi,其中 a mod b 是数字 a 除以数字 b 的余数。

要获得第一组测试的满分,解决 n = 2, 1 ≤ ki ≤ 2000 的问题就足够了。

要获得第二组测试的满分,解决 n = 2, 1 ≤ ki ≤ 200000 的问题就足够了。

要获得第三组测试的满分,解决 1 ≤ n ≤ 5000、1 ≤ ki ≤ 5000 的问题就足够了。

输出

在第一行打印一个数字——最佳顺序中“坏”对的数量。

如果问题总数不超过 200000,还打印 $$\sum_{k=1}^{n}$$ 行 — 问题的最佳顺序。在每一行上打印两个由一个空格分隔的整数 - 分别是问题所需的资源数量和提出该问题的科学家的数量。 The scientists are numbered from 1 to n in the order of input.

示例

输入 #1

2
2 1 1 1 10
2 3 1 1 10

输出 #1

0
1 1
2 1
3 2
4 2

输入 #2

2
3 10 2 3 1000
3 100 1 999 1000

输出 #2

2
10 1
23 1
49 1
100 2
99 2
98 2

注意

在第一个样本中,n = 2, k1 = 2, a1, 1 = 1, a1, 2 = 2, k2 = 2, a2, 1 = 3, a2, 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) 没有“坏”对。