logo AlgoBeat OnlineJudge
登录 注册

#214688. 圆环

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

Yuki 是一个喜欢玩游戏的机器人!

Yuki 最喜欢玩的游戏的规则如下:

  • 游戏在一个长度为 的圆环上进行,其中位置 与位置 相邻;初始时,Yuki 的两只手分别位于位置 和位置 ;在游戏过程中,Yuki 可以花费一点体力,将其中一只手移动到相邻的一个位置上。
  • 这个圆环上一共会出现 个音符;在第 秒时,位置 会出现一个音符,此时需要满足 Yuki 有至少一只手位于位置 ,否则 Yuki 将输掉游戏;若 Yuki 完成了所有的要求,那么称她完成了游戏。
  • 保证没有音符重叠;即对于每对满足 的正整数 ,保证
  • 保证每个时刻最多有两个音符;即对于每个正整数 ,保证满足 的正整数 不超过两个。

由于 Yuki 是一个机器人,所以她玩这个游戏很有优势——不论怎么移动,她的手都不会打结,并且她的两只手也可以移动到相同的位置上。

现在,Yuki 想让你帮助她求出,她完成游戏至少要花费多少点体力。容易证明 Yuki 一定可以完成游戏。

输入格式

第一行包含三个整数 ,其中 表示测试点编号。 表示该测试点为样例。

接下来 行,第 行包含两个整数

输出格式

输出一行,包含一个整数,表示她完成游戏所至少要花费的体力的点数。

样例

样例输入 1

0 3 4
1 2
2 3
2 2
3 1

样例输出 1

2

数据范围与提示

样例 2

见下发文件中的

该组样例满足测试点 的限制。

样例 3

见下发文件中的

该组样例满足测试点 的限制。

样例 4

见下发文件中的

该组样例满足测试点 的限制。

样例 5

见下发文件中的

该组样例满足测试点 的限制。

样例 6

见下发文件中的

该组样例满足测试点 的限制。

样例 7

见下发文件中的

该组样例满足测试点 的限制。

数据范围

对于所有测试数据,保证:

  • 对于每对满足 的正整数
  • 对于每个正整数 ,满足 的正整数 不超过两个。

::cute-table{tuack}

测试点编号 特殊性质
A
B
A
B
A
B
  • 特殊性质 A:对于每个正整数 ,保证满足 的正整数 的数量为偶数。
  • 特殊性质 B:对于每个正整数 ,保证满足 的正整数 不超过一个。