SGOI第七次竞赛试题

注意事项：
　　1、本次SGOI采用网页方式提交，请大家完成后登录网站：　　　　　http://fzyzsgoi.yeah.net或http://www.fzyz.net/sgoi/submit.asp按要求提交你的程序。（提交次数有限）。
　　2、如无法访问上述网站，请发EMAIL至sgoi@shuguang.net。

要求：
　　1、将源程序用WINZIP打包后作为附件发送；
　　2、在邮件主题中注明：SGOI7友谊赛；
　　3、在邮件内容中写明你的：姓名、年段、地区、学校、指导教师或自己的EMAIL地址。

　　　　　　　　　　　　　　　　　试题一览表

题一：音乐厅布置（Hall）

【背景】

　　建成于1891年的纽约卡内基音乐厅（Carnegie Hall）音响效果绝佳，是世界最著名的音乐厅之一，它有很大的舞台，在这个音乐季，他们正准备演出莫扎特（Mozart）的歌剧《后宫诱逃（Die Entfuehrung aus dem Serail）》。剧中某些场景需要搭建一座土耳其皇宫，正如我们所熟悉的阿拉伯建筑风格，"皇宫"由一些高度、直径都相同的圆柱支撑，其中一些柱子和外墙相接，另一些在皇宫内部；所有外墙上的柱子向皇宫内的一侧的地面上都放有灯（假设灯放在柱子的圆心这个点上），灯光可以照射到皇宫内的任何部分，除非被东西遮挡。"皇宫"外围是灰白色的"石壁"，就是两根柱子中间的部分，并且总在两根柱子圆心的连线上。墙壁都有一定的透光度，使得内部灯光散射出来，晶莹剔透。因为半透明，墙壁不太厚，相对于柱子的直径，我们忽略墙壁的厚度，如右图所示，灰色部分表示皇宫内部，蓝色部分表示柱子内部。皇宫的横截面总是凸多边形，上方有和横截面几何形状一模一样且厚度密度都均匀的平顶（图中线段围住的部分，即以各个外墙上的柱子的圆心为顶点的凸多边形）。演出时场景布置当然要富丽堂皇、尽善尽美，因此他们请天才的你来解决他们的一切问题。

【问题】

　　1、 舞台上不能放置太重的东西，柱子、墙壁都是用塑料等轻的材料做的，不能承重。而皇宫的平顶面积大，还是挺重的，不能直接压在这些材料上，只能通过舞台顶部的架子悬挂。当然，悬挂用的绳子是越细越少越好。他们提出一个大胆的想法，让你只用一根非常坚固的绳子，悬挂起整个屋顶。你的任务就是，找到平顶上一个恰当的点，使得从这个点可以把平顶平稳的吊起来。

　　2、 布景时，布景师们在顶部的架子上走动，时常不小心碰到一些工具，掉下去砸坏了道具。因此，他们观察了几个经常放工具的点，并告诉你这些点在舞台上投影的位置，请你判断一下这些东西竖直掉下会对"皇宫"造成什么影响。某物品从某个点落下，如果恰好砸在柱子上（内），输出C；砸到墙壁上，输出L；砸到皇宫内空地，输出I；落到皇宫外，输出O；如果砸到物体的交界处，只需按照CLIO的顺序输出第一个。

　　3、 演出时，录音师为演出制作环绕立体声录音。为了排除墙壁隔音的影响，他们在"皇宫"里的地面上也放置了几个麦克风。但为了不影响灯光照射，麦克风必须放在灯光照射不到的地方。出于声学的考虑，录音师建议了几个适合放置麦克风的位置，请你从光学的角度，分析一下其中那些位置可以放置，哪些不可以。如某个麦克风可以放置，那么输出1，否则输出0。
　　我们用一个平面直角坐标系表示舞台地面，给你的数据包括：柱子总数、直径，"皇宫"高度，平顶厚度，每根柱子中心的坐标，以及问题2、问题3要判断点的坐标。
　　如果你能圆满解决了音乐厅面临的三个难题，演出后，你将被授予"最佳协作奖"。

【输入】

　　第1行有四个整数，是柱子总数p、直径d、"皇宫"高度h1和平顶厚度h2，数据中间都用一个空格隔开。
　　以下p行，每行有两个实数,，数据间用一个空格隔开，是第i根柱子的中心坐标。
　　第p+2行是一个整数n，表示问题2要判定的顶点个数。
　　以下n行，每行有两个实数,，是问题2要判定的第i个点的坐标，数据间用一个空格隔开。
　　第p+n+3行是一个整数m，表示问题3要判定的顶点个数。
　　以下m行，每行有两个实数,，数据间用一个空格隔开，是问题3要判定的第i个点的坐标，并保证这些点都在"皇宫"的可用空间内。
　　数据范围：1≤p≤1000，0≤n、m≤1000。输入数据不要判错。

【输出】

　　输入文件必须严格包含三行，分别是三个问题的结果，如果某个问题没有完成，也必须输出一个空行。
　　第1行包含两个实数x,y，表示可以悬挂平顶的点的坐标，数据间用一个空格间隔，保留三位小数。
　　第2行包括n个字母，是CLIO之一，表示问题2的结果，数据间用一个空格间隔。
　　第3行，输出m个数，是0或者1，表示问题3的结果，数字间用一个空格间隔。

【样例输入】

　　7 1 110 10
　　-3 3
　　3 2
　　-2 -2
　　3 -1
　　0 0
　　1 1
　　-1 1
　　4
　　-4 1
　　-2 1
　　0 0
　　0 2.5
　　2
　　1 -1
　　0 0.55

【样例输出】

　　0.015 0.545
　　O I C L
　　0 1

题二：折线（Line）

【问题】

　　给定一个m行n列的方格阵，每个方格边长为1。要从方格阵左上方的顶点（0，0）走到右下方的顶点（m，n），中间有若干个格子是障碍物，无法通过。人可以从（x1，y1）走到（x2，y2），当且仅当（x1<=x2）且（y1<=y2）且线段（x1，y1）-（x2，y2）不穿过任意一个障碍方格。求最短路长度。

【输入】

　　文件的第一行包括3个用空格分开的正整数m，n。以下是一个邻接矩阵A，1表示表示障碍。

【输出】

　　文件只有一行。文件应只一个精确到小数点后面2位小数的实数，表示最短路径的长度。

【样例输入】

　　3 　4
　　0 0 1 0
　　0 1 0 0
　　0 0 0 1

【样例输出】

　　5.47

【提示】

以下是示例数据的一种答案：
　　注意：图中红色的部分告诉我们，尽管路线不能穿越障碍方格，但是可以沿着障碍方格行进。
　　数据范围：
　　　　　　1≤m，n≤80，输入数据无需判错。

题三：最佳路线（Bestline）

【背景】

　　塞内加尔是非洲的一个小国家，你也许很难在世界地图上找到它，甚至你有可能从未听说过它--它实在是个太小、太贫穷的国家了。可是，就是这个人口不足900万、全国仅有2个标准足球场地的小国，在2002韩日世界杯的非洲区预选赛中脱颖而出，取得了世界杯决赛圈的入场券（幸好，去年中国队也进入了世界杯决赛圈，不然可就丢脸了）。

　　在塞内加尔全国球迷欣喜若狂，世界足球行家大跌眼镜的同时，塞内加尔足协却发现自己面临着一个颇为尴尬的问题--说起来令人不可思议，由于打非洲区预选赛时四处征战，加上足协经营不力，现在足协的预算以几近赤字--也就是说，塞内加尔足协支付不起从本国乘飞机到达韩国参加世界杯的费用！经过三思，塞内加尔足协向非洲足联递交了一份《关于减免球队旅行费用》的申请；可是--众所周知的，非洲足联也是惨淡经营，幸好非洲足联秘书长神通广大，弄来了M张优惠乘机券：每张优惠券可以作用于一条航线，使全队通过此航线的费用减半；多张优惠券用于同一条线路，其效果叠加--即在一条航线上用两张优惠券，其费用降为原费用的1/4，依此类推。

【问题】

　　塞内加尔足球队要从塞内加尔国家机场出发，途经一些中转机场，最后要到达韩国釜山机场。为了合理地分配各张优惠券，使得所需费用最少，塞内加尔足协找到了你，请你编程解决这个问题。

【输入】

　　第1行有两个数N、M（0<N<=70，0<=M<=20）并用空格隔开，分别表示包括起点（塞内加尔国家机场）、终点（韩国釜山机场）的机场数，以及塞内加尔足协现有的优惠券数量。
　　从第2行到第N+1行起，每行有N个数，其中第I行的第J个数代表从机场I到机场J所需费用；为零的数代表两机场无航线。
　　假设起点标号为1，终点标号为N。

【输出】

　　第1行仅有一个数（保留两位小数），代表所求得的从机场1到机场N的最小费用；
　　第2行打印航线，每两个机场间用"->"连接（参见样例输出）；
　　输入数据保证从塞内加尔机场可达釜山机场。

【样例输入】

　　5 2
　　0 0 80 96 0
　　70 0 72 54 0
　　18 0 0 99 82
　　72 18 71 0 0
　　69 0 0 70 0

【样例输出】

　　81.00
　　1->3->5

题四：仓库管理员的难题（Move）

【背景】

　　沃尔玛公司是世界零售业的一大巨头。Sam是该公司在华盛顿某会员店的仓库管理员，他每天的工作就是监督搬运工们将一箱又一箱的货物堆放到仓库里指定的位置上。可以想象，这是一份多么轻松而高薪的工作，Sam非常珍惜和热爱这份工作，在他的管理下，仓库的各项工作都井井有条，Sam也因此多次受到上司的表扬。
　　有一次，上司忽然安排Sam加班，原来是有一大批货物需要及时入库。Sam立即联系几位搬运工协助工作，然而不巧的是这些搬运工不是因为身体不适就是去度假了，都不能前来。这可急坏了Sam，因为按照公司的规定，如果不能按时完成上司的任务他就会被无条件解雇--这当然是Sam所不愿意的。于是，他只好自己做一回搬运工。

【问题描述】

　　右图为一个仓库的示意图，周围的黑色方块表示仓库围墙或者已经摆放好的货物（我们统称之为障碍）。蓝色圆点是Sam的初始位置，灰色方块就是要搬运的货物，左侧的小方块表示货物应堆放的位置。
　　仅当以下条件成立时，货物才可被Sam从一个位置推动到相邻的另一个位置：

　　1、 目标位置没有障碍；
　　2、 当前位置、目标位置、Sam所处位置在同一行或同一列；
　　3、 Sam位于与货物相邻的方格上。

　　当然，货物被推动后，Sam就占据了货物原来的位置。同时，他在走动时也不得穿越障碍物和货物或者进入它们的内部。
　　正如我们前面提到的，沃尔玛公司作为世界零售业的巨头，这整批货物的量相当巨大，于是，Sam不可能一次搬完，而只能将他们一件一件地搬运到指定的位置。可想而知，对于Sam这个白领来说，一个人搬运这么多货物，劳动强度多么巨大。为了节省体力，Sam希望能够为每件货物寻找一种方案，使得能够在推动货物移动的步数最少的前提下，将货物堆放到指定的位置。请你编程帮助他解决眼下这个难题。

【数据输入】

　　数据的第一行是两个正整数n、m (2≤m,n≤40)，代表这个仓库有n行m列。
　　第二行到第n+1行，每行有m个值为0或1的数，分别代表仓库的空地和障碍，每两个数之间用一个空格隔开。
　　第n+2行有6个正整数x0,y0、x1,y1、x2,y2，分别表示初始时货物所处位置、货物的指定堆放位置、初始时Sam所处位置。x0,y0,x1,y1,x2,y2一定不和障碍物重叠，输入数据无需判错。

【数据输出】

　　如果Sam无论如何也不可能完成任务，那么就输出"Sam will lose his job."
　　如果有解，输出数据的第一行包括一个整数，表示Sam推动该货物移动的最小步数。
　　第二行是一条满足条件的货物移动路径（格式参见示例输出，如果存在多条这样的路径，只要输出其中的一条）。

【样例输入】

　　7 7
　　0 1 1 0 0 1 1
　　0 1 0 0 0 0 1
　　0 1 1 1 0 0 1
　　0 0 0 1 0 0 1
　　1 1 1 1 0 0 1
　　1 0 0 0 0 0 1
　　1 1 1 1 1 1 1
　　2 4 6 2 2 3

【样例输出】

　　8
　　(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(6,5)->(6,4)->(6,3)->(6,2)

题五：简单的积木搭建问题(Tower)

【背景】

　　有足够多的等大积木用于搭建高度（层数）为h的塔。塔的每层都是排列紧密的一列积木。将一座塔的各层的积木数连续写出组成的序列{}称为塔的表达式。一座塔不会倒塌的条件是：

　　（一）塔的每层至少有一块积木（>0，i=1..n）；
　　（二）每层的积木块数均与相邻层相差1（-=±1，i=1..n-1）；
　　（三）塔的底层必须有m块积木（=m）。两座塔与不同，当且仅当塔的层数不同（m<>n）或对于特定的层i（1<= i <=min{m，n}），有<>。与此类似的，两座塔<不同，当且仅当塔的层数相同（m=n）且对于特定的层i（1<= i <= m），有<，且对于所有的j，1<=j<i，均有。

【任务一】

　　给定m与h，求可能的塔的种类。

【任务二】

　　在任务一的基础上，把所有塔按照表达式大小排序（具体的序列排序定义略，参照等长字符串的大小比较方式），计算第k种塔的表达式。

【输入方式】

　　从文件Tower.in读入数据，文件的第一行是3个正整数m，h，c。随后的c行每行包括两个正整数，（i=1..c），为的长度，求第种塔的表达式。

【输出方式】

　　结果打印到文件Tower.out中，输出文件的第一行是符合条件的塔的数量，以下c行，每个表达式占一行，表达式顺序按照读入命令的顺序，表达式里的数用空格隔开。

【样例输入】

　　4 4 5
　　1 8
　　1 6
　　1 1
　　1 2
　　1 4

【样例输出】

　　8
　　4 5 6 7
　　4 5 4 5
　　4 3 2 1
　　4 3 2 3
　　4 3 4 5

【提示】

　　1<=m<=10000，1<=h<=1600，1<=c<=100，1<=<=10^100，输入数据无需判错。