宜昌市一中青少年奥林匹克信息学联赛提高组试题汇总.doc

宜昌市一中青少年奥林匹克信息学联赛提高组试题汇总NOM-NOIP2007-t1-t3命题人:GatesMax GeniiMax Deathice 审题人:陈凡 向志勇 陈晓红 测试数据GatesMax GeniiMax Deathice（提高组 三小时完成）说明：由于临时变动，此次模拟赛题目难度有所降低。如有时间可自行加难度，如第二题可以加上输出路径等。关于提交程序的说明： 本次模拟赛采用Cena客户端提交，打开IE浏览器，输入192.168.6.12,下载并运行cenaclient-install.exe文件。提示安装成功后，请在右下脚系统托盘里对应图标上点右键，点“选项”。“选手名称”选“自定义”并输入自己的名字；工作目录定位到以你名字命名的目录，比赛的四个源程序文件就放在这个目录下。关于竞赛中不同语言使用限制的说明一关于使用Pascal语言与编译结果的说明1对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。2允许使用数学库(uses math子句)，以及ansistring。但不允许使用编译开关（最后测试时pascal的范围检查开关默认关闭：$R-,Q-,S-），也不支持与优化相关的选项。相似的资料(book.pas/c/cpp)【问题描述】据说高二某班的物理有两本资料优化方案和高考总复习第一轮100课时。做了一段时间后，就有同学发现这两本资料对应章节有很多内容都是相同的。于是有人就两本资料相应章节的相似程度做了些研究。这里会给出S1和S2两个字符串（均由A-Z这26个字母组成）分别表示两本资料的题目类型，你要做的就是帮忙找到一个字符串S3，既是S1的子串又是S2的子串，并且最长(保证由所给的数据求出的S3是唯一的)。这里的S3即可以表示两本资料的相似度。【输入文件】输入文件book.in有两行。分别是S1和S2（S1和S2的长度均不超过200），表示两书题目类型。【输出文件】输出文件book.out包括两行。第一行是一个数字，为S3的长度。第二行为字符串S3，表示两书的相似度。【输入样例】ACCGGTCGAGTGCGCGGAAGCCGGCCGAAGTCGTTCGGAATGCCGTTGCTCTGTAAA【输出样例】20GTCGTCGGAAGCCGGCCGAA传作业(pass.pas/c/cpp)【问题描述】某十三同学一日上学迟到，此时已经开始上早自习了，所以他只好请同学帮忙把作业传到组长那里。由于刚开学不久，某十三同学还没来得及认识所有同学，所以传作业时只好找熟悉的同学。已知某十三与组长之间有N个他熟悉的同学，并且知道这些同学相互之间间隔的距离。因为每两个同学间传作业都需要下位，所以现在请你帮忙设计一种传作业的方案，使所有同学下位走动的总距离最小。【输入文件】输入文件pass.in 的第1行，为一个正整数N(N=98)，表示某十三与组长之间的他所熟悉的同学人数。接下来N+2行，每行有N+2个正整数(integer)，其中第I行的第J个数代表第I个同学与第J个同学之间的距离（第1个为某十三本人，第2到第N+1个依次为某十三熟悉的同学，第N+2个是组长）。【输出文件】输出文件pass.out包括一行，为一个正整数L，代表最短的总移动距离。【输入样例】30 3 4 5 13 0 6 7 84 6 0 7 65 7 7 0 41 8 6 4 0【输出样例】1数独验证(sodoku.pas/c/cpp)【问题描述】XX学校风靡一款智力游戏，也就是数独（九宫格），先给你一个数独，并需要你验证是否符合规则。具体规则如下:每一行都用到1,2,3,4,5,6,7,8,9，位置不限，每一列都用到1,2,3,4,5,6,7,8,9，位置不限，每33的格子（共九个这样的格子）都用到1,2,3,4,5,6,7,8,9，位置不限，游戏的过程就是用1,2,3,4,5,6,7,8,9填充空白，并要求满足每行、每列、每个九宫格都用到1,2,3,4,5,6,7,8,9。如下是一个正确的数独:【输入文件】(sodoku.in)输入n个数独，你来验证它是否违反规则.第一行为数独个数，第二行为第一个数独，之后为第二个，至第n个.每个之间有一个空格【输出文件】(sodoku.out)若正确则输出”Right”若不正确则输出”Wrong” 输出一个换一行【样例输入】25 8 1 4 9 3 7 6 29 6 3 7 1 2 5 8 42 7 4 8 6 5 9 3 11 2 9 5 4 6 3 7 84 3 6 1 8 7 2 9 57 5 8 3 2 9 1 4 68 9 2 6 7 1 4 5 36 1 5 9 3 4 8 2 73 4 7 2 5 8 6 1 91 2 3 4 5 6 7 8 92 3 4 5 6 7 8 9 13 4 5 6 7 8 9 1 24 5 6 7 8 9 1 2 35 6 7 8 9 1 2 3 46 7 8 9 1 2 3 4 57 8 9 1 2 3 4 5 68 9 1 2 3 4 5 6 79 1 2 3 4 5 6 7 8【样例输出】RightWrong【数据规模】1=n=20 （输入的数独个数）不论输入的数独是错误的还是正确的,数据都保证每个数在1-9之间,即只会出现因为有相同的数而导致违反规则,而不会因为数字超出了1-9的范围而违反规则.开平方数(radical.pas/c/cpp)【问题描述】编写程序计算一个多项式的值的开平方数。只会出现+和号【输入文件】(radical.in)第一排输入N第二排输入长度为N的字符串为算式【输出文件】(radical.out)多项式的值的开平方数，根号用#表示(若无因数可开平方为整数则#没有数字，如输入“3+3”，输出“#6”,若开平方数为整数则不输出#，如输入“3+6”， 输出“3”)【样例输入】932+201-33【样例输出】10#2【数据规模】1=多项式的值=400，且为整数1=数字长度=100，且为整数1=N=100下次上什么课(classes.pas/c/cpp)【问题描述】NOIP2007有上课的方式有四种，BOSS向上课、小红上课、自己做题或考试。（1）如果这次是BOSS向上课，那么下次会是小红上课或考试。（2）如果这次是小红上课，那么下次会是自己做题。（3）如果这次是自己做题，那么下次会是小红上课或BOSS向上课（4）如果这次是考试，那么下次会是自己做题或BOSS向上课。【输入文件】(classes.in)第一排输入2个数据H、T，H=1表示这次是BOSS向上课,H=2表示这次是小红上课,H=3表示这次是自己做题,H=4表示这次是考试.【输出文件】(classes. out)输出2个数据P、S，p为T次课后最有可能上的课的编号H（若可能性一样输出编号H小的），S为T次课后一共有多少种可能。【样例输入】3 4【样例输出】2 9【数据规模】1=T=25抢金块(point.pas/c/cpp)【问题描述】地面上有一些格子，每个格子上面都有金块，但不同格子上的金块有不同的价值，你一次可以跳S至T步 (2=ST=10) 如果S=2,T=4.你就可以跳2步,3步或4步,告诉你这些后,你从第一个格子起跳,必须跳到最后一个格子上,请你输出最多可以获得的金块的总价值.【输入文件】第一行是格子个数,第二行是S和T s不等于t第三行是每个格子上的金块价值. 第一个为第一个格子上的价值,默认从第一个格子起跳,必须跳到最后一个格子上,也就是说第一个格子上的金块和最后一个格子的金块你就可以直接获得了.【输出文件】输出最多可以获得的金块的总价值.和走法 如果走法不止一种 输出 -1【样例输入】102 34 5 8 2 8 3 6 7 2 9【样例输出】361 3 5 8 10/数据解释：跳1,3,5,8,10分数:4+8+8+7+9=36/【数据规模】格子数目10002=ST=10最后金块的总价值在int范围内.每个金块的价值在int范围内.化学方程式(chem.pas/c/cpp)【问题描述】102班每天要写化学方程式，现在要想办法批改方程式。方程式中反应物的顺序可以不一样，中间可以有空格。不会出现沉淀和气体符号和反应条件。错误有系数不对（下标不对，如CO2为CO3也算系数不对。反应物或生成物中不会出现元素相同，系数不同的化学式，如：CO和CO2不会一起出现在反应物或生成物中），化学式错误，缺少反应物，两边元素不守恒。【输入文件】(chem.in)第一排输入N,M第二排输入长度为N的字符串为正确方程式第三排输入长度为M的字符串为要批改方程式【输出文件】(chem.out)正确输出RIGHT错误第一排输出WRONG，第二排输出错误原因（只系数不对为1，其他错误和有两个以上错误为2）【样例输入1】3