#P11709. 「KTSC 2020 R2」魔法转盘
「KTSC 2020 R2」魔法转盘
题目背景
请使用 C++17 或 C++20 提交本题
你需要在程序开头加入如下代码:
#include <vector>
long long findMinClicks(int M, int R, std::vector <std::pair<int, int> > P);
题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T1「 마법의 다이얼」
题目描述
在持续的算法学习中感到疲惫的京根,想去另一个世界休息几天。有一天,他听说了一个通往另一个世界的门的位置,于是他去了那里。那里有一扇通往另一个世界的门,但门被锁住了,门上有一个巨大的转盘锁。
这个锁由上下排列的 个转盘组成。每个转盘有 个格子,可以左右旋转到不同的格子。每个格子上可能有一个点,也可能没有点。每个转盘至少有一个点。通过旋转转盘,使得在某个位置上所有格子都垂直对齐有点,门就会打开。每个转盘可以单独旋转。由于转盘非常重,旋转起来很费力,所以希望旋转的总格子数最少。
上图展示了一个转盘的例子。最佳方法之一是:将第一个转盘向左旋转一格,第二个转盘向左旋转两格,第三个转盘向右旋转一格,第四个转盘不旋转,总共旋转 格。
给定转盘的大小和点的位置,编写一个程序,计算最少需要旋转多少格才能打开门。点的位置由转盘编号和格子编号的坐标表示。最上面的转盘是 号转盘,向下编号依次增加,最下面的转盘是 号转盘。为了确定格子编号,任意相同位置的(即垂直对齐的)格子编号为 ,向右编号依次增加。 号格子的左边是 号格子。给定的点的坐标不会重复。
你需要实现以下函数:
long long findMinClicks(int M, int R, vector< pair<int, int> > P);
- 参数 是转盘的数量。
- 参数 是每个转盘的格子数。
- 参数 是一个包含 个整数对的数组。每个整数对的第一个数是转盘编号,第二个数是格子编号。给定的点的坐标不会重复。
- 函数
findMinClicks()
返回打开门所需的最少旋转格子数。
该函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。
输入格式
示例评测程序按以下格式读取输入:
- 第 行:整数
- 第 行:整数 ,其中 是第 个点的坐标。
输出格式
示例评测程序将输出你的代码中 findMinClicks()
函数返回的值。
7 4 20
1 3
0 2
2 6
3 8
3 1
2 0
1 8
4
提示
对于所有输入数据,满足:
详细子任务附加限制及分值如下表所示。
Subtask | 分值 | 约束 |
---|---|---|
无附加限制 |
本题满分为 分。