Lazarus中文社区

 找回密码
 立即注册(注册审核可向QQ群索取)

QQ登录

只需一步,快速开始

版权申明
查看: 6487|回复: 2

第二十届全国信息学奥林匹克竞赛(2003)第一试

[复制链接]

该用户从未签到

发表于 2010-8-17 16:17:44 | 显示全部楼层 |阅读模式
木棒游戏
【问题描述】
这是一个很古老的游戏。用木棒在桌上拼出一个不成立的等式,移动且只移动一根木棒使得等式成立。现在轮到你了。
(图见附件)

【任务】
从文件读入一个式子。
如果移动一根木棒可以使等式成立,则输出新的等式,否则输出No。

【说明和限制】
1.式子中只会出现加号和减号(包括负号),并且有且仅有一个等号,不会出现括号、乘号或除号,也不会有++,--,+-或-+出现。
2.式子中不会出现8个或8个以上的连续数字。
3.你只能移动用来构成数字的木棒,不能移动构成运算符(+ -=)的木棒,所以加号、减号、等号是不会改变的。移动前后,木棒构成的数字必须严格与图2中的0~9相符。
4.修改前的等式中的数不会以0 开头,但允许修改后的等式中的数以数字0开头。
(图二见附件)

【输入数据】
从文件 game.in 中读入一行字符串。该串中包括一个以“#”字符结尾的式子(ASCII 码35),式子中没有空格或其他分隔符。输入数据严格符合逻辑。字符串的长度小于等于1000。
注意:“#”字符后面可能会有一些与题目无关的字符。

【输出数据】
输出结果到文件game.out,输出仅一行。
如果有解,则输出正确的等式,格式与输入的格式相同(以“#”结尾,中间不能有分隔符,也不要加入多余字符)。
如果无解,则输出“No”(N大写,o 小写)。

【输入样例1】
1+1=3#
【输出样例1】
1+1=2#

【输入样例2】
1+1=3+5#
【输出样例2】
No

【输入样例3】
11+77=34#
【输出样例3】
17+17=34#

题2

文本编辑器
【问题描述】
很久很久以前,DOS3.x的程序员们开始对EDLIN感到厌倦。于是,人们开始纷纷改用自己写的文本编辑器……
多年之后,出于偶然的机会,小明找到了当时的一个编辑软件。进行了一些简单的测试后,小明惊奇地发现:那个软件每秒能够进行上万次编辑操作(当然,你不能手工进行这样的测试)!于是,小明废寝忘食地想做一个同样的东西出来。
你能帮助他吗?
为了明确目标,小明对“文本编辑器”做了一个抽象的定义:
文本:由0个或多个ASCII码在闭区间[32, 126]内的字符(即空格和可见字符)构成的序列。
光标:在一段文本中用于指示位置的标记,可以位于文本首部,文本尾部或文本的某两个字符之间。
文本编辑器:为一个包含一段文本和该文本中的一个光标的,并可以对其进行如下六条操作的程序。如果这段文本为空,我们就说这个文本编辑器是空的。

操作名称             输入文件中的格式      功能
MOVE(k)                      Move k              将光标移动到第k个字符之后,如果k=0,将光标移到文本开头
INSERT(n, s)              Insert n S            在光标处插入长度为n的字符串s,光标位置不变,n≥1
DELETE(n)                Delete n              删除光标后的n个字符,光标位置不变,n≥1
GET(n)                       Get n                 输出光标后的n个字符,光标位置不变,n≥1
PREV()                        Prev                 光标前移一个字符
NEXT()                         Next                 光标后移一个字符

比如一个空的文本编辑器依次执行操作INSERT(13, “Balanced tree”),
MOVE(2),DELETE(5),NEXT(),INSERT(7, “ editor”),MOVE(0),GET(16)后,会输出“Bad editor tree”。
你的任务是:
l 建立一个空的文本编辑器。
l 从输入文件中读入一些操作并执行。
l 对所有执行过的GET操作,将指定的内容写入输出文件。

【输入文件】
输入文件 editor.in 的第一行是指令条数t,以下是需要执行的t 个操作。其中:
为了使输入文件便于阅读,Insert 操作的字符串中可能会插入一些回车符,请忽略掉它们(如果难以理解这句话,可以参考样例)。
除了回车符之外,输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。
这里我们有如下假定:
l MOVE操作不超过50000个,INSERT和DELETE操作的总个数不超过4000,PREV和NEXT操作的总个数不超过200000。
l 所有INSERT插入的字符数之和不超过2M(1M=1024*1024),正确的输出文件长度不超过3M字节。
l DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。
l 输入文件没有错误。
对 C++选手的提示:经测试,最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒。

【输出文件】
输出文件editor.out 的每行依次对应输入文件中每条GET指令的输出。
【样例输入】
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22

【样例输出】
.\/.
abcde^_^f.\/.ghijklmno

题3

卫星探测
【问题描述】
美国中央情报局最近获悉某国建造了核试验基地,正准备进行危险的核试验。据已经潜入基地的间谍报告,该基地是一个凸多边形的结构,围栏均使用特殊材料制成,可以有效地反射各种核辐射,防止核泄露。但是,在这紧要关头,突然与间谍失去了联络,这一状况使美国总统焦急万分,因为该国试验成功将会造成核扩散,对世界和平非常不利。幸好中央情报局拥有着世界上最先进的科技,他们能通过军事卫星发出探测波,根据基地围栏的反射信号强度来判断探测波是
否和基地围栏相交。
现在中央情报局请你写个程序,控制卫星发出的探测波,根据返回的信号来确定该核试验基地的确切规模以及位置,以便能够实施进一步的行动。
由于间谍在核试验基地内部失去了联络,所以卫星以间谍失去联系的坐标为中心建立坐标系,基地一定包含(0,0)这个坐标中心。假设基地的每个顶点的坐标都是整数。每次卫星在基地同一平面内发出直线形探测波。如果反射信号非常弱,
则表示这条直线与基地围栏只有1个交点;如果反射信号稍强一些,则表示这条直线与基地围栏只有2个交点;如果没有反射信号,则说明该直线和基地围栏没有交点。这里特殊的是,卫星只能发出与x轴或者y轴平行的直线,而我们知道
在基地的围栏中并没有与选取的x轴和y轴平行的围栏,所以我们可以通过反射回来的信号来确定直线和基地围墙的交点。

【交互方法】
本题是一道交互式题目,你的程序应当和测试库进行交互,而不得访问任何文件。测试库提供3组函数,分别用于程序的初始化,与测试库的交互,以及程序的结果返回。它们的用法于作用如下:
l prog_initialize必须先调用,但只能调用一次,用作初始化测试库;
l 测试库提供两个函数ask_x 和ask_y 作为与测试库交互的方式。其中ask_x(x0, y1, y2)的的作用是询问直线x=x0和多边形的交点,ask_y(y0,x1, x2)的作用是询问直线y=y0 与多边形的交点。这里如果函数的返回值是0,表示直线和多边形围栏没有交点;如果返回值是1,表示直线和多边形围栏有一个交点,并从x1、x2或y1、y2中返回交点的坐标(两个值相同);如果返回值是2,那么表示直线与多边形交了两个点,并从x1、x2或y1、y2中返回交点的坐标(两个值不同);l 最后的一组函数是你的程序用来向测试库返回结果的。这里包括返回多边形面积的ret_area(s),返回多边形顶点数目的ret_n(n),返回多边形顶点的ret_vertex(x, y)。需要注意的事,这里ret_area 是必须先于ret_n调用的,而ret_n又是必须先于ret_vertex调用的。不合适的调用方式将会强制你的程序非法退出。这里你需要在调用ret_n 后调用n次ret_vertex来按照逆时针顺序返回多边形的顶点,但需要注意的是,如果你用 ret_n 返回的结果是错误的,那么测试库将会马上终止你的程序并不接受下面的结果;同样的,如果ret_vertex中返回了错误的结果,那么测试库也会马上终止你的程序。如果ret_vertex 的结果均是正确的,那么测试库将会在你返回最后一个顶点坐标后终止你的程序。

【对使用Pascal 选手的提示】
你的程序应当使用如下的语句引用测试库。
uses detect_lib;
测试库使用的函数原型为:
procedure prog_initialize;
function ask_x(const x0: longint; var y1, y2: double): longint;
function ask_y(const y0: longint; var x1, x2: double): longint;
procedure ret_area(const s: double);
procedure ret_n(const n: longint);
procedure ret_vertex(const x, y:longint);

【对使用C/C++选手的提示】
建立一个工程把文件detect_lib.o包含进来,然后在程序头加上一行:
#include <detect_lib.h>
测试库使用的函数原型为:
void prog_initialize();
int ask_x(int x0, double *y1, double *y2);
int ask_y(int y0, double *x1, double *x2);
void ret_area(double s);
void ret_n(int n);
void ret_vertex(int x, int y);

【数据说明】
如果凸多边形的坐标如右图所示(见附件),那么一种可能得满分的调用方案如下:
Pascal选手的调用方法           C/C++选手的调用          方法说明
prog_initialize;                         prog_initialize();           初始化程序
ask_x(-6, y1, y2);                    ask_x(-6, &y1, &y2);     返回值1,y1=2,y2=2
ask_x(-5, y1, y2);                    ask_x(-5, &y1, &y2);     返回值2,y1=3.4,y2=-5
ask_y(2, x1, x2);                      ask_y(2, &x1, &x2);      返回值2,x1=-6,x2=16
ask_y(-20, x1, x2)                    ask_y(-20, &x1, &x2)    返回值0,x1、x2中的值无意义
ret_area(241.5);                      ret_area(241.5);           返回面积
ret_n(5);                                  ret_n(5);                        返回n
ret_vertex(8, -9);                     ret_vertex(8, -9);           返回顶点(8, -9)
ret_vertex(16, 2);                    ret_vertex(16, 2);          返回顶点(16, 2)
ret_vertex(-1, 9);                     ret_vertex(-1, 9);          返回顶点(-1, 9)
ret_vertex(-6, 2);                     ret_vertex(-6, 2);          返回顶点(-6, 2)
ret_vertex(-5, -5);                   ret_vertex(-5, -5);          返回顶点(-5, -5)

注意,该例子只是对库函数的使用说明,并没有算法上的意义。
这里n最大为200,x、y坐标在[-10000, 10000]这个区间内。

【评分方法】
如果你的程序有下列情况之一,得0分:
l 访问了任何文件(包括临时文件)或者自行终止;
l 非法调用库函数;
l 让测试库异常退出。
否则每个测试点你的得分按这样来计算:包括顶点数提交正确的1分,面积提交正确的2分,顶点坐标完全正确的2分,分数累计。剩下的5分将根据你调用ask_x和ask_y的总次数进行评判,公式如下:(见附件)
这里x为你的程序调用的ask_x和ask_y的次数,score为你的得分。

【你如何测试自己的程序】
1. 在工作目录下建立一个文件叫做detect.in,文件的第一行包括一个整数n 为顶点的数目,以下n 行每行两个整数按照逆时针方向给出凸多边形的顶点坐标;
2. 执行你的程序,此时测试库会产生输出文件detect.log,该文件中包括了你程序和库交互的记录和最后的结果;
3. 如果程序正常结束,detect.log的最后一行包含一个整数,为你的程序的分数;
4. 如果程序非法退出,则我们不保证detect.log中的内容有意义。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册(注册审核可向QQ群索取)

x
回复

使用道具 举报

  • TA的每日心情
    奋斗
    2022-6-24 15:56
  • 签到天数: 10 天

    [LV.3]偶尔看看II

    发表于 2010-10-16 02:13:08 | 显示全部楼层
    貌似我们当年的题目呀,不过就记得第一题了。。。。
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    发表于 2010-11-15 00:00:59 | 显示全部楼层
    program matches;

    var
    f:array[0..2000] of longint;
    i,j,he,n,ans,x:longint;
    begin
    readln(n);
    f[0]:=6;
    f[1]:=2;
    f[2]:=5;
    f[3]:=5;
    f[4]:=4;
    f[5]:=5;
    f[6]:=6;
    f[7]:=3;
    f[8]:=7;
    f[9]:=6;
    for i:=10 to 2000 do
    begin
    x:=i;
    while x>0 do
    begin
    f:=f+f[x mod 10];
    x:=x div 10;
    end;
    end;
    ans:=0;
    n:=n-4;
    for i:=0 to 1000 do
    begin
    if f<=n then
      begin
      for j:=0 to 1000 do
       begin
       if (f+f[j])<=n then
       he:=i+j;
       if f+f[j]+f[he]=n then inc(ans);
       end;
      end;
    end;
    write(ans);
    readln;
    readln;

    end.
          第一题
    回复 支持 反对

    使用道具 举报

    *滑块验证:

    本版积分规则

    QQ|手机版|小黑屋|Lazarus中国|Lazarus中文社区 ( 鄂ICP备16006501号-1 )

    GMT+8, 2024-6-23 06:18 , Processed in 0.037396 second(s), 9 queries , Redis On.

    Powered by Discuz! X3.4

    Copyright © 2001-2021, Tencent Cloud.

    快速回复 返回顶部 返回列表