广度优先搜索训练题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
广度优先搜索训练题
&&广度优先搜索训练题
阅读已结束，下载文档到电脑
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩3页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢广度优先搜索训练题 三亿文库
广度优先搜索训练题
广度优先搜索训练题 一、奇怪的电梯 源程序名
LIFT.PAS 可执行文件名
LIFT.EXE 输入文件名
输出文件名
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,??)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？
输入 输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。 输出 输出文件仅一行，即最少按键次数,若无法到达，则输出-1。
样例 LIFT.IN 5 1 5 3 3 1 2 5
LIFT.OUT 3 二、师生树问题： 假设用表示字符A，B有师生关系且B是A的1代学生（字符A~Z，0~9共36个）。若给出，则C是A的2代学生。若给出，，，，，则E是A的2代学生，如果无最后一个关系，则E是A的4代学生。如果某人没有老师，则称为师祖。所有具有师生关系的人组成一个师生树。 任务：从数据文件中输入一组关系，求出师生树的总数并分别输出各师生树的成员，输出各师生树的成员时，首先输出师祖，再依次输出各代学生，各代学生间用“，”分隔，同代学生中按ASCII码由小到大顺序输出。如果在求解的过程中找不出师生树则输出“NO ANSWER”。 输入格式： 从键盘输入数据文件名 输入数据文件格式如下： 5
------表示有N组关系
------每行有一组关系，共N行
输出格式：在显示器上输出 1：A，BE，C
------ 表示该师生树成员表 2：D，E TOTAL=2
------ 表示师生树总数
三、字串变换 [问题描述]:
已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:
A1$ -> B1$
A2$ -> B2$
规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ ?。
例如：A$＝'abcd' B$＝'xyz'
变换规则为：
‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’
则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：
‘abcd’->‘xud’->‘xy’->‘xyz’
共进行了三次变换，使得 A$ 变换为B$。 [输入]:
键盘输人文件名。文件格式如下：
A1$ B1$ \\
|-> 变换规则
所有字符串长度的上限为 20。[输出]:
输出至屏幕。格式如下：
若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出\[输入输出样例] b.in:
y yz 屏幕显示：
四、网络传输问题
问题描述 (提交文件：network.pas / network.exe)
在一个特殊的网络系统中有N台计算机，某个有关国家安全的信息需要在一个绝对安全的环境中从计算机1传递到计算机N。其中，我们规定以下安全策略：
A： 每台计算机都与某些计算机相连，且为无向连通。
B： 某计算机α需要安全验证，而这些验证必须由计算机β上取得，但计算机β并不一定和计算机α相连。
C： 该信息必须在经过计算机β时即取得计算机α的安全验证，则之后可以进入计算机α，否则不能进入计算机α。
D： 信息只能在相邻的计算机之间传递，即使在取得β验证后也不能在α与β不相连的情况下直接到达α。
E： 因为信息的重要程度，我们保证信息最终必能抵达计算机N。
由于网络传输需要时间，而每经过一台计算机消耗时间定为1，题目则要求求出传输该信息所需要的最短时间。 输入（INPUT.TXT）:
第一行为N(N≤80）。之后的第2到第N+1行分别描述计算机1到N，每行第一个数字为计算机i需要的安全验证的来源计算机编号j，在1到N 之间，若为0则无需验证。之后紧跟着的是与计算机i相连的计算机的编号，一直读到该行结束。 输出(OUTPUT.TXT):
输出文件仅一行，为传递所需要的最短时间。
五、过河（GDSOI-2000） 问题描述
农夫每天去种地都要过一条河，这条河很宽，过河要走上面的木桩。木桩有N去，排成一排，从左岸延伸到左岸，编号从1到N。左岸在1号桩的左边，右岸在N号桩的右边。但这些木桩会定时升降，因此，每天他都花不少时间在过河上。所以他想找一种最快过河的方法。 在时刻0，农夫在左岸，他要在最短时间内到达右岸。在任何时刻，每一去桩都只能处于升或降的其中一种状态。升起的桩才可以站上去，农夫只能站在升起的桩上或岸上。 每一支桩在时刻0都是降的状态，接着升起A分钟，降下B分钟，再升起A分钟后，再降下B分钟，这样一直交替升降下去。例如，A=2，B=3的桩，在时刻0降，时刻1、2升，在时刻3、4、5降，等等。A和B是常数时间。而且对于每一去桩都可能不同。 设在时刻T农夫站在P桩，那在时刻T+1，农夫能走到P桩左右5个桩上或岸上，也可以原地不动，当然桩要可站的。例如，在5号桩，他能走到1，2，3，4，5，6，7，8，9，10号桩，或到左岸。请帮农夫找一种能最快到达右岸的方法。 数据输入 从当然目录下的文本文件“river.dat”读入数据。 第一行是桩的数目N（5<N<=1000）。接下来的N行每一行有两个整数A和B（1<=A,B<=5），用一个空格分开。按从1到N的顺序描述每一支桩的升降间隔时间。 数据输出 答案输出到当前目录下的文本文件“river.out”中。 只有一行，即最早到达右岸的时刻。当不可能到达右岸时，输出“NO” 输入输出样例 输入文件：river.dat 10 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 输出文件：river.out 4
六、造房子的学问 【问题描述】
小木屋看来已被荒置很多年了，Z4决定首先把它修葺一下，由最健壮的hongyan总负责。其余的人各自到到上去砍伐木材。
一些细微工作结束后，hongyan决定在木屋中加一条顶梁柱，但是其他人提供的木材长度参差不齐，幸运的是几何功底扎实的他，利用已有的工具造出了一把尺子。
hongyan首先选取了了一条最好的木材，然后他可以对这条木材作如下几种操作： 1． 接上分别由jakrinchose，立方，worm提供的木材(由于岛上资源丰富,这些木材是无限的)，木材的长度会不损耗的增加。
2.用尺子在木材上截去该尺子长度的一段，当然截开后的两段木材依然可以利用。
3.把木材对半截断，木材长度变为原来的一半。
另外jakrinchose等提供用于拼接的木材由于质量一般（谁说的？！)，不能直接使用为顶梁柱。
现在hongyan 想知道，通过这几种操作，是否能造出需要的长度的顶梁柱（当然他手中的“最好的木材”不能完全被截去，也就是说在操作的过程中不能把“最好的木材”完全扔掉以至长度为0！）假如可以，最少需要多少不工序？ 【输入文件】 输入文件wood.in有5行，第一行两个数n,m(1<=n,m<=32767)分别表示该木材原来的长度，和需要的长度.第2至4行各一个数分别是jakrinchose，立方，worm提供用于拼接的木材长度L1，L2，L3(L1，L2，L3<=32767)，最后一行也是一个数，表示尺子的长度L(L<n)。 （Z4是喜欢整数的人，所以所有的数据是整数，同时，对半截断的木材多出来的非整数部分，将作为多余的成分删去，也就是该操作后，木材的长度可以用div 2来运算；同时，任何时候，木材长度都不应大于32767）。 【输出文件】
输出文件wood.out仅一行，假如不能造出需要的长度，则输出“No solution.”否则输出最少需要的工序数。 【输入样例】 100 81 10 24 40 1 【输出样例】 3 （样例注解：３的结果是截出１，再加上两次４０）
七、这不是错误，而是特点（Buggs）[ GDOI-99 ] 提交文件：bugs.exe 输入文件：bugs.dat 输出文件：bugs.out 问题描述 对于一个软件公司来说，在发行一个新软件之后，可以说已经完成了工作。但是实际上，许多软件公司在发行一个新产品之后，还经常发送补丁程序，修改原产品中的错误（当然，有些补丁是要收费的）。 微硬公司就是这样的一个软件公司。今年夏天，以发行了一个新的字处理软件之后，到现在他们已经编写了许多补丁程序。仅仅在这个周末，他们就用新编写的补丁程序解决了软件中的一个大问题。而在每一个补丁程序修改软件中的某些错误时，有可能引起软件中原来存在的某些错误重新发作。发生这种情况是因为当修改一个错误时，补丁程序利用了程序中约定的特别行为，从而导致错误的重新产生。 微硬公司在他们的软件中一共发现了N个错误B={B1，B2，??，Bn}，现在他们一共发送了M个补丁程序P1，P2，??，Pm。如果想要在软件中应用第Pi号补丁程序，则软件中必须存在错误Bi+<=B，并且错误Bi-<=B必须不存在（显然，Bi+∩Bi-为空集）。然后，这个补丁程序将改正错误Fi-<=B（如果错误存在的话），并且产生新的错误Fi+<=B（同样，+-Fi∩Fi为空集）。 现在，微硬公司的问题只有一个，他们给出一个原始版本的软件，软件包含了B中的所有错误，然后按照某一顺序在软件中应用补丁程序（应用某个补丁程序时，软件必须符合该补丁程序的应用条件，且运行该程序需要一定的时间）。问怎样才能最快地改在软件中的所有错误（即为修正所有错误而运行的补丁程序的总时间最短）？ 输入格式 数据从输入文件中读入，文件的第一行包含两个整数N和M，分别表示软件中的错误个数和发送的补丁个数。其中N和M满足条件：1<=N<=20,1<=M<=200 接下来的M行（即第2行至第M+1行）按顺序描述了M个补丁程序的情况。第J行描述第J-1号补丁程序。每一行包含一个整数（表示在软件中应用该补丁程序所需的时间，单位为秒）和两个N个字符的字符串（中间均用一个空格分开）。 第一字符串描述了应用该补丁程序（第J-1号）的条件，即说明在软件中某错误应该存在还是不应该存在。字符串的第i个字符，如果是“+”，表示在软件中必须存在Bi号错误，如果是“-”，表示软件中错误Bi不能存在；如果是“0”，则表示错误Bi存在或不存在均可（即对应用该补丁程序没有影响）。 第二个字符串描述了应用该补丁程序（第J-1号）后的效果，即应用补丁程序后，哪些错误被修改好了，而又产生了哪些新错误。字符串的第i个字符，如果是“+”，表示产生了一个新错误Bi，如果是“-”，表示软件中错误Bi被修改好了；如果是“0”，则表示错误Bi不变（即原来存在，则仍然存在；原来不存在，则也不存在）。
输出格式 答案输出到文件中。 请你找到一个应用补丁程序的最优顺序，修改软件中的所有错误，并且所用的时间最少。注意，每个补丁程序是可以应用多次的。 如果存在这样一个序列，请在输出文件的第一行输出应用补丁程序的总时间（单位为秒）；如果找不到这样一个序列，请在输出文件的第一行输出-1。 输入输出样例 输入文件：bugs.dat 3 3 1 000
-++ 输出文件：bugs.out 8
样例二 输入文件：bugs.dat 4 1 7 0-0+
---- 输出文件：bugs.out -1
联系客服：cand57</广度优先搜索训练题；一、奇怪的电梯；源程序名LIFT.PAS可执行文件名LIFT.E；呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯；输入文件共有二行，第一行为三个用空格隔开的正整数；输出文件仅一行，即最少按键次数,若无法到达，则输；LIFT.OUT3；二、字串变换[问题描述]:；已知有两个字串A$,B$及一组字串变换的规则（至；规则的含义为：在A＄中的子
广度优先搜索训练题 一、奇怪的电梯 源程序名
LIFT.PAS 可执行文件名
LIFT.EXE 输入文件名
输出文件名
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,??)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？
输入 输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。 输出 输出文件仅一行，即最少按键次数,若无法到达，则输出-1。
样例 LIFT.IN 5 1 5 3 3 1 2 5
LIFT.OUT 3
二、字串变换 [问题描述]:
已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:
A1$ -> B1$
A2$ -> B2$
规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ ?。
例如：A$＝'abcd' B$＝'xyz'
变换规则为：
‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’
则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：
‘abcd’->‘xud’->‘xy’->‘xyz’
共进行了三次变换，使得 A$ 变换为B$。 [输入]:
键盘输人文件名。文件格式如下：
A1$ B1$ \\
|-> 变换规则
所有字符串长度的上限为 20。[输出]:
输出至屏幕。格式如下：
若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出\[输入输出样例] b.in:
y yz 屏幕显示：
三、网络传输问题
问题描述 (提交文件：network.pas / network.exe)
在一个特殊的网络系统中有N台计算机，某个有关国家安全的信息需要在一个绝对安全的环境中从计算机1传递到计算机N。其中，我们规定以下安全策略：
A： 每台计算机都与某些计算机相连，且为无向连通。
B： 某计算机α需要安全验证，而这些验证必须由计算机β上取得，但计算机β并不一定和计算机α相连。
C： 该信息必须在经过计算机β时即取得计算机α的安全验证，则之后可以进入计算机α，否则不能进入计算机α。
D： 信息只能在相邻的计算机之间传递，即使在取得β验证后也不能在α与β不相连的情况下直接到达α。
E： 因为信息的重要程度，我们保证信息最终必能抵达计算机N。
由于网络传输需要时间，而每经过一台计算机消耗时间定为1，题目则要求求出传输该信息所需要的最短时间。 输入（INPUT.TXT）:
第一行为N(N≤80）。之后的第2到第N+1行分别描述计算机1到N，每行第一个数字为计算机i需要的安全验证的来源计算机编号j，在1到N 之间，若为0则无需验证。之后紧跟着的是与计算机i相连的计算机的编号，一直读到该行结束。 输出(OUTPUT.TXT):
输出文件仅一行，为传递所需要的最短时间。
四、过河（GDSOI-2000） 问题描述
农夫每天去种地都要过一条河，这条河很宽，过河要走上面的木桩。木桩有N去，排成一排，从左岸延伸到左岸，编号从1到N。左岸在1号桩的左边，右岸在N号桩的右边。但这些木桩会定时升降，因此，每天他都花不少时间在过河上。所以他想找一种最快过河的方法。 在时刻0，农夫在左岸，他要在最短时间内到达右岸。在任何时刻，每一去桩都只能处于升或降的其中一种状态。升起的桩才可以站上去，农夫只能站在升起的桩上或岸上。 每一支桩在时刻0都是降的状态，接着升起A分钟，降下B分钟，再升起A分钟后，再降下B分钟，这样一直交替升降下去。例如，A=2，B=3的桩，在时刻0降，时刻1、2升，在时刻3、4、5降，等等。A和B是常数时间。而且对于每一去桩都可能不同。 设在时刻T农夫站在P桩，那在时刻T+1，农夫能走到P桩左右5个桩上或岸上，也可以原地不动，当然桩要可站的。例如，在5号桩，他能走到1，2，3，4，5，6，7，8，9，10号桩，或到左岸。请帮农夫找一种能最快到达右岸的方法。 数据输入 从当然目录下的文本文件“river.dat”读入数据。 第一行是桩的数目N（5<N<=1000）。接下来的N行每一行有两个整数A和B（1<=A,B<=5），用一个空格分开。按从1到N的顺序描述每一支桩的升降间隔时间。 数据输出 答案输出到当前目录下的文本文件“river.out”中。 只有一行，即最早到达右岸的时刻。当不可能到达右岸时，输出“NO” 输入输出样例 输入文件：river.dat 10 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 输出文件：river.out 4
五、造房子的学问 【问题描述】
小木屋看来已被荒置很多年了，Z4决定首先把它修葺一下，由最健壮的hongyan总负责。其余的人各自到到上去砍伐木材。
一些细微工作结束后，hongyan决定在木屋中加一条顶梁柱，但是其他人提供的木材长度参差不齐，幸运的是几何功底扎实的他，利用已有的工具造出了一把尺子。
hongyan首先选取了了一条最好的木材，然后他可以对这条木材作如下几种操作： 1． 接上分别由jakrinchose，立方，worm提供的木材(由于岛上资源丰富,这些木材是无限的)，木材的长度会不损耗的增加。
2.用尺子在木材上截去该尺子长度的一段，当然截开后的两段木材依然可以利用。
3.把木材对半截断，木材长度变为原来的一半。
另外jakrinchose等提供用于拼接的木材由于质量一般（谁说的？！)，不能直接使用为顶梁柱。
现在hongyan 想知道，通过这几种操作，是否能造出需要的长度的顶梁柱（当然他手中的“最好的木材”不能完全被截去，也就是说在操作的过程中不能把“最好的木材”完全扔掉以至长度为0！）假如可以，最少需要多少不工序？ 【输入文件】 输入文件wood.in有5行，第一行两个数n,m(1<=n,m<=32767)分别表示该木材原来的长度，和需要的长度.第2至4行各一个数分别是jakrinchose，立方，worm提供用于拼接的木材长度L1，L2，L3(L1，L2，L3<=32767)，最后一行也是一个数，表示尺子的长度L(L<n)。 （Z4是喜欢整数的人，所以所有的数据是整数，同时，对半截断的木材多出来的非整数部分，将作为多余的成分删去，也就是该操作后，木材的长度可以用div 2来运算；同时，任何时候，木材长度都不应大于32767）。 【输出文件】
输出文件wood.out仅一行，假如不能造出需要的长度，则输出“No solution.”否则输出最少需要的工序数。 【输入样例】 100 81 10 24 40 1 【输出样例】 3 （样例注解：３的结果是截出１，再加上两次４０）
三亿文库包含各类专业文献、幼儿教育、小学教育、外语学习资料、专业论文、行业资料、文学作品欣赏、应用写作文书、广度优先搜索训练题87等内容。　
　图练习题(答案)_政史地_高中教育_教育专区。《图》练习题一、单项选择题 1...(D,F)},则从顶点 A 开始对 该图进行广度优先搜索,得到的顶点序列可能为( ... 　广度优先搜索练习题很多问题都可以用广度优先搜索 广度优先搜索进行处理,如翻币问题(参见归纳策略中的移动棋子问题)、最短路径问题 广度优先搜索 (参见动态规划)等。... 　广度优先搜索训练题 一、奇怪的电梯源程序名 可执行文件名 输入文件名 输出文件名 LIFT.PAS LIFT.EXE LIFT.IN LIFT.OUT 呵呵, 有一天我做了一个梦, 梦见了... 　广度优先搜索初级题目及代码分享广度优先搜索初级题目及代码分享隐藏&& 广度优先搜索初级题目 邮递员问题 题目描述: 有一个邮递员要在 n 个城市之间来回送信。但有... 　注意力广度训练 暂无评价 22页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 广度优先搜索专题训练(题目) 隐藏&&... 　广度优先搜索专题训练(题目,11月22日修改) 隐藏&& 广度优先搜索专题训练(报告命名:年级 专业 姓名+专题名字 专业+姓名 专题名字) 广度优先搜索专题训练(报告命名:... 　广度优先搜索练习_理学_高等教育_教育专区。。。广度优先搜索练习 1、营求(save...NOIP2005普及组复赛试题... 10页 1下载券&#169;2014 Baidu 使用百度前必读 | 文... 　考试题目-宽度优先搜索_学科竞赛_高中教育_教育专区。第一题 跳棋(1.PAS) 题目:跳棋的原始状态如下图。其中&0&表示空格,&-&表示白子,&+&表示黑子,&1― ―...广度优先搜索训练题 南京廖华
广度优先搜索训练题
广度优先搜索训练题 一、奇怪的电梯 源程序名
LIFT.PAS 可执行文件名
LIFT.EXE 输入文件名
输出文件名
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,??)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？
输入 输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。 输出 输出文件仅一行，即最少按键次数,若无法到达，则输出-1。
样例 LIFT.IN 5 1 5 3 3 1 2 5
LIFT.OUT 3 二、师生树问题： 假设用表示字符A，B有师生关系且B是A的1代学生（字符A~Z，0~9共36个）。若给出，则C是A的2代学生。若给出，，，，，则E是A的2代学生，如果无最后一个关系，则E是A的4代学生。如果某人没有老师，则称为师祖。所有具有师生关系的人组成一个师生树。 任务：从数据文件中输入一组关系，求出师生树的总数并分别输出各师生树的成员，输出各师生树的成员时，首先输出师祖，再依次输出各代学生，各代学生间用“，”分隔，同代学生中按ASCII码由小到大顺序输出。如果在求解的过程中找不出师生树则输出“NO ANSWER”。 输入格式： 从键盘输入数据文件名 输入数据文件格式如下： 5
------表示有N组关系
------每行有一组关系，共N行
输出格式：在显示器上输出 1：A，BE，C
------ 表示该师生树成员表 2：D，E TOTAL=2
------ 表示师生树总数
三、字串变换 [问题描述]:
已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:
A1$ -> B1$
A2$ -> B2$
规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ ?。
例如：A$＝'abcd' B$＝'xyz'
变换规则为：
‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’
则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：
‘abcd’->‘xud’->‘xy’->‘xyz’
共进行了三次变换，使得 A$ 变换为B$。 [输入]:
键盘输人文件名。文件格式如下：
A1$ B1$ \\
|-> 变换规则
所有字符串长度的上限为 20。[输出]:
输出至屏幕。格式如下：
若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出\[输入输出样例] b.in:
y yz 屏幕显示：
四、网络传输问题
问题描述 (提交文件：network.pas / network.exe)
在一个特殊的网络系统中有N台计算机，某个有关国家安全的信息需要在一个绝对安全的环境中从计算机1传递到计算机N。其中，我们规定以下安全策略：
A： 每台计算机都与某些计算机相连，且为无向连通。
B： 某计算机α需要安全验证，而这些验证必须由计算机β上取得，但计算机β并不一定和计算机α相连。
C： 该信息必须在经过计算机β时即取得计算机α的安全验证，则之后可以进入计算机α，否则不能进入计算机α。
D： 信息只能在相邻的计算机之间传递，即使在取得β验证后也不能在α与β不相连的情况下直接到达α。
E： 因为信息的重要程度，我们保证信息最终必能抵达计算机N。
由于网络传输需要时间，而每经过一台计算机消耗时间定为1，题目则要求求出传输该信息所需要的最短时间。 输入（INPUT.TXT）:
第一行为N(N≤80）。之后的第2到第N+1行分别描述计算机1到N，每行第一个数字为计算机i需要的安全验证的来源计算机编号j，在1到N 之间，若为0则无需验证。之后紧跟着的是与计算机i相连的计算机的编号，一直读到该行结束。 输出(OUTPUT.TXT):
输出文件仅一行，为传递所需要的最短时间。
五、过河（GDSOI-2000） 问题描述
农夫每天去种地都要过一条河，这条河很宽，过河要走上面的木桩。木桩有N去，排成一排，从左岸延伸到左岸，编号从1到N。左岸在1号桩的左边，右岸在N号桩的右边。但这些木桩会定时升降，因此，每天他都花不少时间在过河上。所以他想找一种最快过河的方法。 在时刻0，农夫在左岸，他要在最短时间内到达右岸。在任何时刻，每一去桩都只能处于升或降的其中一种状态。升起的桩才可以站上去，农夫只能站在升起的桩上或岸上。 每一支桩在时刻0都是降的状态，接着升起A分钟，降下B分钟，再升起A分钟后，再降下B分钟，这样一直交替升降下去。例如，A=2，B=3的桩，在时刻0降，时刻1、2升，在时刻3、4、5降，等等。A和B是常数时间。而且对于每一去桩都可能不同。 设在时刻T农夫站在P桩，那在时刻T+1，农夫能走到P桩左右5个桩上或岸上，也可以原地不动，当然桩要可站的。例如，在5号桩，他能走到1，2，3，4，5，6，7，8，9，10号桩，或到左岸。请帮农夫找一种能最快到达右岸的方法。 数据输入 从当然目录下的文本文件“river.dat”读入数据。 第一行是桩的数目N（5<N<=1000）。接下来的N行每一行有两个整数A和B（1<=A,B<=5），用一个空格分开。按从1到N的顺序描述每一支桩的升降间隔时间。 数据输出 答案输出到当前目录下的文本文件“river.out”中。 只有一行，即最早到达右岸的时刻。当不可能到达右岸时，输出“NO” 输入输出样例 输入文件：river.dat 10 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 输出文件：river.out 4
六、造房子的学问 【问题描述】
小木屋看来已被荒置很多年了，Z4决定首先把它修葺一下，由最健壮的hongyan总负责。其余的人各自到到上去砍伐木材。
一些细微工作结束后，hongyan决定在木屋中加一条顶梁柱，但是其他人提供的木材长度参差不齐，幸运的是几何功底扎实的他，利用已有的工具造出了一把尺子。
hongyan首先选取了了一条最好的木材，然后他可以对这条木材作如下几种操作： 1． 接上分别由jakrinchose，立方，worm提供的木材(由于岛上资源丰富,这些木材是无限的)，木材的长度会不损耗的增加。
2.用尺子在木材上截去该尺子长度的一段，当然截开后的两段木材依然可以利用。
3.把木材对半截断，木材长度变为原来的一半。
另外jakrinchose等提供用于拼接的木材由于质量一般（谁说的？！)，不能直接使用为顶梁柱。
现在hongyan 想知道，通过这几种操作，是否能造出需要的长度的顶梁柱（当然他手中的“最好的木材”不能完全被截去，也就是说在操作的过程中不能把“最好的木材”完全扔掉以至长度为0！）假如可以，最少需要多少不工序？ 【输入文件】 输入文件wood.in有5行，第一行两个数n,m(1<=n,m<=32767)分别表示该木材原来的长度，和需要的长度.第2至4行各一个数分别是jakrinchose，立方，worm提供用于拼接的木材长度L1，L2，L3(L1，L2，L3<=32767)，最后一行也是一个数，表示尺子的长度L(L<n)。 （Z4是喜欢整数的人，所以所有的数据是整数，同时，对半截断的木材多出来的非整数部分，将作为多余的成分删去，也就是该操作后，木材的长度可以用div 2来运算；同时，任何时候，木材长度都不应大于32767）。 【输出文件】
输出文件wood.out仅一行，假如不能造出需要的长度，则输出“No solution.”否则输出最少需要的工序数。 【输入样例】 100 81 10 24 40 1 【输出样例】 3 （样例注解：３的结果是截出１，再加上两次４０）
七、这不是错误，而是特点（Buggs）[ GDOI-99 ] 提交文件：bugs.exe 输入文件：bugs.dat 输出文件：bugs.out 问题描述 对于一个软件公司来说，在发行一个新软件之后，可以说已经完成了工作。但是实际上，许多软件公司在发行一个新产品之后，还经常发送补丁程序，修改原产品中的错误（当然，有些补丁是要收费的）。 微硬公司就是这样的一个软件公司。今年夏天，以发行了一个新的字处理软件之后，到现在他们已经编写了许多补丁程序。仅仅在这个周末，他们就用新编写的补丁程序解决了软件中的一个大问题。而在每一个补丁程序修改软件中的某些错误时，有可能引起软件中原来存在的某些错误重新发作。发生这种情况是因为当修改一个错误时，补丁程序利用了程序中约定的特别行为，从而导致错误的重新产生。 微硬公司在他们的软件中一共发现了N个错误B={B1，B2，??，Bn}，现在他们一共发送了M个补丁程序P1，P2，??，Pm。如果想要在软件中应用第Pi号补丁程序，则软件中必须存在错误Bi+<=B，并且错误Bi-<=B必须不存在（显然，Bi+∩Bi-为空集）。然后，这个补丁程序将改正错误Fi-<=B（如果错误存在的话），并且产生新的错误Fi+<=B（同样，+-Fi∩Fi为空集）。 现在，微硬公司的问题只有一个，他们给出一个原始版本的软件，软件包含了B中的所有错误，然后按照某一顺序在软件中应用补丁程序（应用某个补丁程序时，软件必须符合该补丁程序的应用条件，且运行该程序需要一定的时间）。问怎样才能最快地改在软件中的所有错误（即为修正所有错误而运行的补丁程序的总时间最短）？ 输入格式 数据从输入文件中读入，文件的第一行包含两个整数N和M，分别表示软件中的错误个数和发送的补丁个数。其中N和M满足条件：1<=N<=20,1<=M<=200 接下来的M行（即第2行至第M+1行）按顺序描述了M个补丁程序的情况。第J行描述第J-1号补丁程序。每一行包含一个整数（表示在软件中应用该补丁程序所需的时间，单位为秒）和两个N个字符的字符串（中间均用一个空格分开）。 第一字符串描述了应用该补丁程序（第J-1号）的条件，即说明在软件中某错误应该存在还是不应该存在。字符串的第i个字符，如果是“+”，表示在软件中必须存在Bi号错误，如果是“-”，表示软件中错误Bi不能存在；如果是“0”，则表示错误Bi存在或不存在均可（即对应用该补丁程序没有影响）。 第二个字符串描述了应用该补丁程序（第J-1号）后的效果，即应用补丁程序后，哪些错误被修改好了，而又产生了哪些新错误。字符串的第i个字符，如果是“+”，表示产生了一个新错误Bi，如果是“-”，表示软件中错误Bi被修改好了；如果是“0”，则表示错误Bi不变（即原来存在，则仍然存在；原来不存在，则也不存在）。
输出格式 答案输出到文件中。 请你找到一个应用补丁程序的最优顺序，修改软件中的所有错误，并且所用的时间最少。注意，每个补丁程序是可以应用多次的。 如果存在这样一个序列，请在输出文件的第一行输出应用补丁程序的总时间（单位为秒）；如果找不到这样一个序列，请在输出文件的第一行输出-1。 输入输出样例 输入文件：bugs.dat 3 3 1 000
-++ 输出文件：bugs.out 8
样例二 输入文件：bugs.dat 4 1 7 0-0+
---- 输出文件：bugs.out -1
联系客服：cand57</