导线和开关.docVIP

回专题模式 回学习阶段模式 【题目名称、来源】 导线和开关switch.pas《1995-IOI-5》 【问题描述】 如 图5．6－1）所示，具有3根导线的电缆把A区和B区连接起来。在A区3根 导线标以1，2，3;在B区导线1和３被连到开关3，导线2连到开关1。 一般说来，电缆含ｍ（1≤ｍ ≤90）根导线，在A区标以1，2，．．．ｍ。在B 区有ｍ 个开关，标为1，2，．．．ｍ。每一根导线都被严格地连到这些开关中的某一个上; 每一个开关上可以连有0根或多根导线。 测量： 你的程序应作某些测量来确定，导线和开关怎样连。 每个开关或处于接通或处于断开状态，开关的初始状态为断开。我们可用一个探头（probe）P在A区进行测试:如果探头点到某根导线上，当且仅当该导线连到处接通状态的开关时，灯L才会点亮。 你的程序从标准输入（standard input）读入一行以得到数字ｍ;然后可以通过向标准输出（standard output）写入一行以发出命令（共3种命令）。每种命令的开头是一个大写字母: ○测试导线命令T:T后面跟一个导线标号; ○改变开关状态命令C:C后面跟一个开关标号; ○完成命令D:D后面跟的是一个表列（LIST），该表列中的第ｉ个元素代表与导线ｉ相连的开关号。 在命令T和C之后，你的程序应从标准输入（standard input）读入一行。 若开关状态能使灯亮，则命令T的回答应是Y;反之，回答应是N。命令C的作用是改变开关的状态（若原来是接通则变为断开;若原来是断开则变为接通）。对C命令的回答是作为一种反馈信号。 你的程序可以给出一系列命令，将T命令与C命令以任意顺序混合使用。最后给出命令D，并结束。你的程序给出的命令总数应不大于900。 注意: 为了在此任务中能正确使用标准输入（ standard input ）和标准输出（ standard output）。若你使用pascal，请不要使用其中的CRT单元（unit CRT）。 举例 下图给出了一个实例，对应于上图，这是一个有8条命令的对话。 Standard Output Standard Input C3 T 1 T 2 T 3 C 3 C 2 T 2 D 3 1 3 3 Y Y N Y N Y N 【所属专题】 二分法、递归、交互式 【适合学习阶段】 第二阶段、第三阶段 【解题思路】 问题分析： 《信息学奥林匹克题解精编》 要准确的估算你的算法在最差的情况下可能发出命令的总数最多是多少，然后可以 发现，仅仅对开关使用二分法还是不能够满足要求（命令数 900）。这就启发我们将开关 和导线同时使用二分法相结合：所有待连接的导线分为两个集合x,y。x初始化为 x [1..m]，y [ ]；然后是开关的二分，查找是一分为二的进行的。当前待连接的所有开关 被我们近似平均得分为两部分，前一半开后一半关。用C命令将前一半开关的状态改变， 用T命令对对初始化了的集合x中的导线（即所有当前待连接的导线）测试，根据当前 前一半开关的状态和终端的反应，将x的一部分移到y中去，使x中含有的导线一定接在 前一半开关中，y中含有的导线一定连在后一半那开关中，这就将待连接的导线分为两部分， 然后将前一半开关和x看作子问题进行递归调用操作，知道剩下一个开关就将所有当前 待连接的导线接到这个开关上，或者是当前待连接的导线集合为空。 存储结构： 集合 【测试数据】 【源程序】