算法竞赛入门

背景

请先进入下方 Online Judge，使用自己的账号登录后查看并提交题目。

题目一：活泼的纯情小姑娘

题目描述

去年，冰精琪露诺在上课时偷偷使用了符卡冻符「Perfect Freeze」，结果被老师狠狠教训了一顿。但她不长记性，还是想再玩一次。

这一次，琪露诺冻结了 N 个弹幕（$1 \le N \le 10000$），并把它们排成一列，从第一个开始按周期报数。现在她忘记了到底冻结了多少个弹幕，只记得四种不同的报数周期下，最后一个弹幕（第 N 个）报到数分别是多少。请你根据这些信息，帮她算出冻结的弹幕总数。

设最后一个弹幕报到的数为 N 对周期取模的余数。具体地：

• 以 $A_x$ 为报数周期，最后一个弹幕报到的数为 $A_y$，即 $N \bmod A_x = A_y$；
• 以 $B_x$ 为报数周期，最后一个弹幕报到的数为 $B_y$，即 $N \bmod B_x = B_y$；
• 以 $C_x$ 为报数周期，最后一个弹幕报到的数为 $C_y$，即 $N \bmod C_x = C_y$；
• 以 $D_x$ 为报数周期，最后一个弹幕报到的数为 $D_y$，即 $N \bmod D_x = D_y$。

题目保证存在一个满足上述全部四个条件的正整数 $N$（$1 \le N \le 10000$）。如果存在多个满足条件的 N，请输出最小的那一个。

输入格式

输入共四行，每行两个整数，分别对应一组（周期，余数）：

1
2
3
4

Ax Ay
Bx By
Cx Cy
Dx Dy

数据范围：

• $1 \le A_x, B_x, C_x, D_x < 20$
• $0 \le A_y < A_x$，$0 \le B_y < B_x$，$0 \le C_y < C_x$，$0 \le D_y < D_x$

输出格式

输出一行一个整数：满足条件的弹幕总数 $N$。若存在多个，输出最小的一个。

样例

1
2
3
4

2 1
6 3
5 1
4 1

1

21

样例解释

取 $N = 21$：

• $21 \bmod 2 = 1$
• $21 \bmod 6 = 3$
• $21 \bmod 5 = 1$
• $21 \bmod 4 = 1$

四个条件全部满足，且不存在比 $21$ 更小的可行答案。

题目二：飞翔在宇宙的不可思议的巫女

题目描述

乐园的巫女博丽灵梦正在梦境世界中穿梭，寻找梦境的管理者哆来咪。众所周知，哆来咪所在的梦境世界，地面上布满了网格，因此可以把梦境世界看作一张带网格的二维地图。博丽灵梦最初位于点 $(0, 0)$，而她想要找到的哆来咪位于点 $(x, y)$。

灵梦每次移动的位移由一个向量 $(a, b)$ 描述：一次移动中，她沿第一坐标移动 $a$ 个单位，同时沿第二坐标移动 $b$ 个单位。初始时灵梦处于静止状态，即 $(a, b) = (0, 0)$。

灵梦连续地进行移动。每一次移动执行以下两个操作：

1. 在当前位移向量 $(a, b)$ 的基础上，必须将 $a$、$b$ 中恰好一个的值增加 $1$；
2. 然后灵梦从点 $(p, q)$ 飞到点 $(p + a, q + b)$。

$a$ 和 $b$ 的值只能增加，不能减少。

由于梦境世界的范围有限，它由矩形 $[0, x] \times [0, y]$ 表示。如果灵梦在某次移动后离开了这个矩形区域，她就会进入不稳定的空间区域并被摧毁。

灵梦可以在任意多次移动之后结束旅程。由于不一定能准确到达哆来咪所在的位置，她希望停在一个有效点上（有效点指落在矩形 $[0, x] \times [0, y]$ 内的点，包含边界），并且该点离目标点 $(x, y)$ 尽可能近。具体地，她希望 $(p - x)^2 + (q - y)^2$ 的值尽可能小。

请你帮助灵梦选择移动的次数，并决定每次移动是增加 a 还是增加 b，使她的终点是一个使 $(p - x)^2 + (q - y)^2$ 最小的有效点。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的一行包含两个整数 $x$ 和 $y$（$1 \le x, y \le 10^8$）——哆来咪所在位置（目标点）的坐标。

输出格式

对每个测试用例，输出一行由字符 X 和 Y 组成的字符串 $s$，描述灵梦的最佳行程。

字符串 $s$ 的长度必须等于移动次数。字符 $s_i$ 描述灵梦在第 $i$ 次移动中的行动：

• 若 $s_i$ = X，则灵梦将 $a$ 增加 $1$，然后用得到的向量进行移动；
• 若 $s_i$ = Y，则灵梦将 $b$ 增加 $1$，然后用得到的向量进行移动。

字符串描述的行程必须满足题目中的全部条件，并且终点到目标点 $(x, y)$ 的欧氏距离平方尽可能小。可以证明，在题目限制下，任意最优答案包含的移动次数都不超过 20000。如果存在多个最优答案，输出其中任意一个。

样例

1
2
3
4
5
6
7
8

7
1 1
2 1
4 2
5 4
3 7
1 100
231 157

1
2
3
4
5
6
7

X
XY
XYX
XYY
YXYY
YYYYYYYYYYYYY
XXXXXXXXXXYYYYYYYYYYYYYYYYX

样例解释

测试用例 1： 字符串 X 描述一次移动。灵梦将 a 增加 1，然后从 (0, 0) 移动到 (1, 0)。到目标点 $(1, 1)$ 的距离平方为 $(1-1)^2 + (0-1)^2 = 1$。

测试用例 2： 字符串 XY 把灵梦准确带到了目标点：

$(0, 0) \to (1, 0) \to (2, 1)$

测试用例 3： 字符串 XYX 描述的移动序列为：

$(0, 0) \to (1, 0) \to (2, 1) \to (4, 2)$

灵梦准确到达了目标点 $(4, 2)$。

测试用例 4： 字符串 XYY 把灵梦带到了点 $(3, 3)$。到目标点 $(5, 4)$ 的距离平方为 $(3-5)^2 + (3-4)^2 = 5$。另一个最优答案，例如 XYX，可以把灵梦带到点 $(4, 2)$。

题目三：芥川龙之介的河童

题目描述

为了增加守矢神社的信仰，八坂神奈子邀请河城荷取为神社修建御柱。一根御柱由若干楼层组成。

荷取的初始资金是 $x$ 个黄瓜（对河童来说是一种非常宝贵的货币）。共有 $n$ 根可供建造的御柱，编号为 $1$ 到 $n$。每根御柱的建造相互独立、互不影响；目前还没有任何御柱开始建造。

为了建造第 $i$ 根御柱的第 $j$ 层，需要花费 $a_{i,j}$ 个黄瓜；建造完成后，荷取会立即收到 $b_{i,j}$ 个黄瓜，并加入她的预算中，可用于建造任何御柱的楼层。注意，同一根御柱的楼层必须按编号从小到大依次建造：必须先建好第 1 层，才能建造第 2 层，依此类推。

由于神奈子非常狡诈，并非所有合同都一定有利可图，甚至可能存在 $a_{i,j} > b_{i,j}$ 的情况（即建造该层反而会亏损）。

荷取可以自由安排建造顺序：她可以在不同御柱之间任意切换，也可以在建造过程中穿插任意数量的其他合同。她不需要建造所有楼层，甚至可以完全不建造任何楼层。

荷取的目标是让其中一根御柱建得尽可能高。请你帮助荷取规划建造方案，求出她能让御柱达到的最大层数，以及能达到该层数的御柱中最小的编号。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 3\times 10^4$），表示测试用例的数量。

每个测试用例的格式如下：

• 第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 2\times 10^5$，$0 \le x \le 10^{18}$）——御柱的数量和初始资金；
• 接下来是 n 根御柱的描述，第 i 根御柱的描述为：
  • 第一行包含一个整数 $m_i$（$1 \le m_i \le 2\times 10^5$）——该御柱最多可建造的层数；
  • 第二行包含 $m_i$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,m_i}$——建造各层需要的花费；
  • 第三行包含 $m_i$ 个整数 $b_{i,1}, b_{i,2}, \ldots, b_{i,m_i}$——建造各层后立即收到的黄瓜数。

其中 $0 \le a_{i,j}, b_{i,j} \le 10^9$。保证所有测试用例的 $m_i$ 之和不超过 $2\times 10^5$。

输出格式

对每个测试用例，输出一行两个整数：荷取能让御柱达到的最大层数 $h$，以及能达到层数 $h$ 的御柱中最小的编号。

样例

1
2
3
4
5
6
7
8
9
10
11
12

2
1 6
4
4 4 2 1
2 4 1 1
2 3
2
4 4
5 5
2
2 20
4 0

1
2

4 1
2 1

样例解释

测试用例 1： 资金足够依次建造唯一一根御柱的全部 4 层，所以答案是 4 1。

测试用例 2： 可以先建造第 2 根御柱的第 1 层（花费 2，得到 4，净赚 2 个黄瓜），此时资金变为 5；再依次建造第 1 根御柱的两层（共花费 8，共得到 10，净赚 2），第 1 根御柱因此达到 2 层；第 2 根御柱最多只有 1 层，所以答案是 2 1。

题目四：只有地藏知晓的哀叹

题目描述

戎璎花正在玩垒石头的游戏。她把 $n$ 堆石子摆成一排，其中第 $i$ 堆里有 $a_i$ 颗石子。魂魄妖梦给了她一个严格递增的序列 $b_1, b_2, \ldots, b_n$，并希望她让 $n$ 堆石子的数量序列恰好变成 $b_1, b_2, \ldots, b_n$，即最终第 $i$ 堆的石子数必须等于 $b_i$。

戎璎花分以下两个阶段完成这个过程：

阶段一（加石子）： 她可以在任意一堆石子中添加任意数量的石子。形式上，对每一堆 $i$，她选择一个非负整数 $x_i$，将 $a_i$ 替换为 $a_i + x_i$。

阶段二（交换）： 她可以重复交换相邻的两堆石子。形式上，她可以执行任意多次（可能为零次）如下操作：选择一个满足 $1 \le i \le n-1$ 的索引 $i$，交换 $a_i$ 与 $a_{i+1}$ 的值。

如果在两个阶段结束后，石子数量序列恰好等于 $b_1, b_2, \ldots, b_n$，则称这个过程是有效的。

求所有有效过程中，阶段二所需操作次数的最小值。如果不存在有效过程，则输出 −1。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。

每个测试用例的格式如下：

• 第一行包含一个整数 $n$（$1 \le n \le 2000$）——石子的堆数；
• 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——每堆石子的初始数量；
• 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_1 < b_2 < \ldots < b_n \le 10^9$）——每堆石子的目标数量。

保证所有测试用例的 $n$ 之和不超过 $2000$。

输出格式

对每个测试用例，输出一行一个整数——在所有有效过程中，阶段二可能执行的最小操作次数；如果不存在有效过程，则输出 −1。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

10
3
1 2 2
1 3 5
3
2 2 1
1 2 3
2
5 1
2 4
6
6 5 4 3 2 1
1 2 3 4 5 6
7
4 7 1 6 2 5 3
1 2 3 4 5 6 7
2
2 1
2 3
4
3 2 2 1
1 2 3 4
4
4 3 2 1
1 3 4 5
5
1 5 4 3 2
2 3 4 5 6
5
10 3 8 6 9
3 6 8 9 10

1
2
3
4
5
6
7
8
9
10

0
2
-1
15
12
0
4
4
3
5

样例解释

测试用例 1： 只需要阶段一。取 $x_1 = 0, x_2 = 1, x_3 = 3$，石子堆变成 $1, 3, 5$。不需要交换，所以答案是 0。

测试用例 2： 两个阶段都需要。取 $x_1 = 0, x_2 = 1, x_3 = 0$，石子堆变成 $2, 3, 1$；然后进行两次交换：[2,3,1] → [2,1,3] → [1,2,3]。带 1 颗石子的那堆必须从第 3 个位置移到第 1 个位置，至少需要两次交换，因此答案是 2。

测试用例 3： 无解。第 1 堆最初有 5 颗石子，而目标序列中的每个数都不超过 4；由于只能加石子不能减，这堆石子不可能等于目标序列中的任何数。因此答案为 −1。

测试用例 4： 不需要加石子，只要把石子堆重新排成递增顺序。相邻交换的最少次数为 15。

测试用例 5： 同样不需要加石子，只要把石子堆重新排序。相邻交换的最少次数为 12。