#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「 마법의 다이얼

题目描述

在持续的算法学习中感到疲惫的京根,想去另一个世界休息几天。有一天,他听说了一个通往另一个世界的门的位置,于是他去了那里。那里有一扇通往另一个世界的门,但门被锁住了,门上有一个巨大的转盘锁。

这个锁由上下排列的 MM 个转盘组成。每个转盘有 RR 个格子,可以左右旋转到不同的格子。每个格子上可能有一个点,也可能没有点。每个转盘至少有一个点。通过旋转转盘,使得在某个位置上所有格子都垂直对齐有点,门就会打开。每个转盘可以单独旋转。由于转盘非常重,旋转起来很费力,所以希望旋转的总格子数最少。

上图展示了一个转盘的例子。最佳方法之一是:将第一个转盘向左旋转一格,第二个转盘向左旋转两格,第三个转盘向右旋转一格,第四个转盘不旋转,总共旋转 44 格。

给定转盘的大小和点的位置,编写一个程序,计算最少需要旋转多少格才能打开门。点的位置由转盘编号和格子编号的坐标表示。最上面的转盘是 00 号转盘,向下编号依次增加,最下面的转盘是 M1M-1 号转盘。为了确定格子编号,任意相同位置的(即垂直对齐的)格子编号为 00,向右编号依次增加。00 号格子的左边是 R1R-1 号格子。给定的点的坐标不会重复。

你需要实现以下函数:

long long findMinClicks(int M, int R, vector< pair<int, int> > P);

  • 参数 MM 是转盘的数量。
  • 参数 RR 是每个转盘的格子数。
  • 参数 PP 是一个包含 NN 个整数对的数组。每个整数对的第一个数是转盘编号,第二个数是格子编号。给定的点的坐标不会重复。
  • 函数 findMinClicks() 返回打开门所需的最少旋转格子数。

该函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

输入格式

示例评测程序按以下格式读取输入:

  • 11 行:整数 NMRN\,M\,R
  • 2N+12 \sim N+1 行:整数 DiCiD_{i}\,C_{i},其中 (Di,Ci)(D_{i}, C_{i}) 是第 ii 个点的坐标。

输出格式

示例评测程序将输出你的代码中 findMinClicks() 函数返回的值。

7 4 20
1 3
0 2
2 6
3 8
3 1
2 0
1 8
4

提示

对于所有输入数据,满足:

  • 1R1091 \leq R \leq 10^{9}
  • 1Nmin(MR,5105)1 \leq N \leq \min(MR, 5\cdot 10^5)
  • 1MN1 \leq M \leq N

详细子任务附加限制及分值如下表所示。

Subtask 分值 约束
11 1010 1N5000,1R50001 \leq N \leq 5000,1 \leq R \leq 5000
22 1515 1M5000,1R50001 \leq M \leq 5000,1 \leq R \leq 5000
33 1616 1N50001 \leq N \leq 5000
44 109109 无附加限制

本题满分为 150150 分。