NOI2002湖南省省队选拔赛第一试试题
试题 沙漠巡宝 Tinux系统 跳蚤 填数游戏
可执行文件名 Program.exe System.exe Jump.exe Number.exe
输入文件名 Program.in System.in Jump.in Number.in
输出文件名 Program.out System.out Jump.out Number.out
分数 50 50 50 50
测试点个数 10 10 10 10
时限 5s 12s 1s 1s
考生注意事项：
l 第一试共4道题，每题50分共200分，考试时间4小时
l 每题按上表要求编译成EXE文件
l 每题用上表的输入文件名读入测试数据，所有的输出按上表要求输出到指定文件
沙漠寻宝
（program.exe）
传说在漫无边际的沙漠中有一个古代城市的废墟，里面埋藏了大量的宝藏。听到这个消息的人一个又一个的前去寻宝，却没有发现一个回来的人。
探险家Jack是冒险者队伍中的后起之秀，它加入冒险者队伍的时间虽然不长，却屡屡依靠自己过人的智慧使自己和队友们脱离了险境。“明知山有虎，偏向虎山行”。 在Jack探险队的宗旨的指引下，Jack和他的队友们踏上了沙漠寻宝的旅程。
“我发现沙漠废墟了。”在一名队员的叫喊声中，Jack隐约看到了一些古代城市的残垣断壁和一个通道。 “一定就是这里了。”Jack带领着大家进入了通道。
然而，不幸的事情发生了。就在Jack他们进入通道的同时，通道的入口“轰”的一声就关闭了。Jack和他的队友走到了通道的尽头，正前方是一个巨大的铁门。最令人奇怪的是，铁门竟然使用的是一个极度先进的带有键盘和显示器的电子密码锁，铁门旁还赫然写着开锁的方法：“想到得到我的宝藏的人们，到这里的路途很辛苦吧！不过这一切很快就会结束的，这个铁门就是你们的葬身之地。除非你们能够计算出我屏幕上程序的结果，并且通过键盘输入进去，这扇门就会打开，里面就是我所有的宝藏”
我们的Jack果然不负众望，他打开了他的行囊，拿出了一个类似保险箱的东西。“没见过吗？这是最新型的笔记本电脑，没有它，我再怎么天才也不可能打开这扇门的。”面对大家疑惑的目光，Jack打开了笔记本电脑的开关。
“这个宝藏主人的程序十分的奇怪，我虽然没见过，但根据我的猜测，它的结构应该是这样的：
程序共包含6种语句：start,end,loop,continue,write,以及?=*形式的语句。
start是程序的开始标志，其对应了一个结束标志end。
loop后面空一格并紧跟了一个表达式*，表达式*的值N表示即将循环N次，对应的循环结束标志也是end。
continue表示程序跳转到当前循环对应的end语句，break表示程序将跳出当前的循环。
write后面空一格并紧跟了一个表达式*，表示要输出表达式*的值，也就是要输入到密码锁中的内容。
?=*是赋值语句，?是变量的名字，*计算出来的值是要给?的。
另外，值得庆幸的是，变量名只允许使用’a’..’z’这26个小写字母，表达式也只允许使用加减乘除四种运算和以及括号，参与运算的也只能是26个变量或者是整数（允许不止一位整数）。表达式不会超过80个字符。”
“希望Jack能很快将锁打开。”大家心里默念着。
给定程序对所有语句的执行次数的总和小于2000000次。
l 输入输出要求
输入文件为program.in，给出了宝藏主人的程序。其中任两条语句用若干个空格或回车符隔开。
输出文件为program.out，是你要输入密码锁的内容。每次输出占一行。
注意：程序中的任何计算都在长整形范围以内，除法为整除，程序不需要判错。
l 输入输出样例
Program.in Program.out
start i=0 j=0 loop 100 i=i+1 j=j+i continue loop 10 write j end end loop 100 j=j+1 break j=j+1 end write jend 5051
Tinux系统
(System.exe)
在dos系统诞生以前，美国曾研究出一种类似的操作系统，名为Tinux系统。但由于硬件设施的制约，Tinux系统有许多的缺点。下面就对Tinux系统作一个简单的介绍：
Tinux系统是Tiger博士为美国军方研制开发的一种操作系统，该系统对文件的存储方式类似于dos系统，像一棵树一样，每一个叶子节点表示一个文件，每一个非叶子节点表示一个目录。其中定义i级子目录表示从根目录开始访问，一直访问到该子目录（不包括该子目录）需要访问的目录的个数为i的目录，所以根目录下的目录为一级子目录，其他的目录以此类推。但是在同一子目录下，受到硬件的制约Tinux系统最多只能够存储k个文件或子目录，也就是说这棵树里面的每一个非叶子节点最多只有k个子节点。这样就导致在文件数量较多的情况下，访问存储在该系统当中的文件A，往往要先访问一系列的子目录，我们称这些子目录为文件A的上级目录。例如下面这一个例子：
Root
l A1
l A2
l A3
l A4
l A4A1
l A4A2
l A4A2A1
l A4A2A2
l A4A3
当我们要访问文件A4A2A1时就必须先访问它的上级目录：一级子目录A4和二级子目录A4A2。
Tinux系统在存储文件时，给每一个子目录都分配了k个指针，分别指向存放在该目录下的每一个文件和每一个目录，因此对文件的访问实质上就是对指针的访问。但是由于硬件原因，这k个指针不尽相同，因此访问它们的时间也不同，访问第i个指针所耗费的时间为 。但是对于两个不同的子目录（不管它们各自属于哪一级目录）而言它们各自所拥有的k个指针是相同的。
Tinux系统最大的缺点是访问一个目录时，必须把该目录下所有的文件读入到内存当中来，这些文件包括在其各级子目录当中的文件，例如上面那一个例子，访问A4那一个目录，就必须把A4A1，A4A2A1，A4A2A2，A4A3这四个文件都读入到内存当中来，访问一个目录所需要的时间为 （x表示该目录及其各级子目录下文件的个数， 表示指向该目录的指针的访问时间）。因此根据上面介绍的访问方法，单独访问一个文件所需要的总时间为访问其所有上级目录（不包括根目录）所需要的时间与访问指向该文件的指针所需要的时间的和，例如上面那一个例子，访问文件A4A2A1需要的时间=访问目录A4的时间+访问目录A4A2的时间+访问指向文件A4A2A1的指针需要的时间。
现在，tiger博士准备将n个文件存储到一个空的Tinux系统当中，希望你帮助他设计一个程序找到一种最优的存储方法，使得单独访问这n个文件所需要的时间总和最小。
l 输入输出要求
输入由文件”system.in”读入。
文件的第一行为两个正整数 ， ，接下来的k行每行有一个正整数 。
输出到文件”system.out”，输出文件仅有一个正整数，表示在最优存储方案下，单独访问这n个文件所需要的时间总和。（结果小于 ）
l 输入输出样例
System.in System.out
4 3354 28
样例的最优存储方案为：
椭圆表示目录，方形表示文件。每一图形里面的数表示访问该文件或目录所需要的时间，所以总费时 。
跳蚤
(jump.exe)
Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。
当确定N和M后，显然一共有MN张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。
l 输入输出要求
输入文件有且仅有一行，包括用空格分开的两个整数N和M。
输出文件有且仅有一行，即可以完成任务的卡片数。
1≤M≤108，1≤N≤M，且MN≤1016。
l 输入输出样例
Jump.in Jump.out
2 4 12
这12张卡片分别是：
(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4),
(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4)
填数游戏
(number.exe)
某商店最近开展了一个答题有奖的促销活动，公司经理将若干道有一定难度的问题贴到了商场的宣传栏内，如果你能够做出其中一道的话，你就能够获得优惠购买商品的权利。一段日子以后，大多数题目都被消费者们找出了答案，可是惟独有一道题目难倒了所有的人，这道题目是这样描述的：
将不同的完全平方数填满 的矩形方格表中的每一个小方格，使得每行、每列的和也是完全平方数（这个和必须小于 ）。希望你找到一种合理的方案。
Tiger希望自己能够获得优惠购物的权利，于是他找到了准备参加NOI2002的你，希望你能够帮他设计一个程序找到一种合理的方案。
l 输入输出要求
输入由文件number.in读入。输入文件中仅有一行，为两个正整数 。
输出到文件number.out。如果有解的话，输出n行，每行有m个数，表示一种合理的填数方案，无解时输出‘No answer’。
l 输入输出样例
Number.in Number.out
2 2 225 1296400 2304
