logo AlgoBeat OnlineJudge
登录 注册

#216322. [蓝桥杯 2026 省 Python B 组] 密室逃脱开关谜题

内存限制：512 MiB 时间限制：3000 ms 标准输入输出
题目类型：VJudge（洛谷） 评测方式：VJudge
上传者： 匿名
提交 提交记录 统计 讨论 题解

题目描述

你被困在一个密室中，面前有一个控制面板，上面有 个开关，控制着密室中的 盏灯。开关编号为 ，灯编号为 。

开关与灯的作用规则如下：

  • 按下第 个开关（），会切换第 盏灯和第 盏灯的状态。
  • 如果这两个编号相同（即 ），则只切换这一盏灯的状态；
  • 切换指：如果灯是关闭的则打开，如果是打开的则关闭。

初始时，所有灯都处于关闭状态。你可以按任意次开关，每个开关可以被多次按下（也可以不按）。

你的目标是让所有灯最终都变为打开的状态。现在，请你计算：最少需要按多少次开关才能做到这一点；如果无论如何操作都无法让所有灯同时打开，则输出 。

输入格式

第一行包含一个整数 ，表示测试数据组数。

接下来 组数据，每组数据占一行，包含两个整数 和 ，分别表示开关的数量和灯的数量。

输出格式

对于每组数据，输出一行，包含一个整数，表示最少需要按开关的次数。如果无法让所有灯都打开，输出 。

样例

样例输入 1

2
4 4
5 5

样例输出 1

3
3

数据范围与提示

【样例说明】

第一组数据：有 个开关（编号 - ）和 盏灯（编号 - ）。

开关控制关系：

  • 开关 ：控制灯 （同一盏）；
  • 开关 ：控制灯 和灯 ；
  • 开关 ：控制灯 和灯 ；
  • 开关 ：控制灯 和灯 .

一种最优方案：按开关 、开关 、开关 ，共按 次。状态变化如下（关 ，开 ）：

状态 控制灯 灯 灯 灯 灯
初始状态 关 关 关
按开关 灯 开 开
按开关 灯 开 关
按开关 灯 开

第二组数据：有 个开关（编号 - ）和 盏灯（编号 - ）。

开关控制关系：

  • 开关 ：控制灯 （同一盏）；
  • 开关 ：控制灯 和灯 ；
  • 开关 ：控制灯 和灯 ；
  • 开关 ：控制灯 和灯 ；
  • 开关 ：控制灯 和灯 。

一种最优方案：按开关 、开关 、开关 ，共按 次。状态变化如下：

状态 控制灯 灯 灯 灯 灯 灯
初始状态 关 关 关
按开关 灯 开
按开关 灯 开
按开关 灯 开

【评测用例规模与约定】

对于 的数据：，；

对于 的数据：，；

对于 的数据：，；

对于 的数据：，。

显示分类标签

编辑器加载中 …
Powered by SYZOJ. Modified by Zemu (UnratedCheater).
项目源码 · 陶片放逐 · 新ICP备2026003452号-2
当前版本：V1.7.2-premium