noip2008普及组复赛试题(附题解).docVIP

全国信息学奥林匹克联赛（NOIP2008）复赛 普及组 一.题目概览 中文题目名称 ISBN号码 排座椅 传球游戏 立体图 isbn seat ball drawing 可执行文件名 isbn seat ball drawing 输入文件名 isbn.in seat.in ball.in drawing.in 输出文件名 isbn.out seat.out ball.out drawing.out 每个测试点时限 1秒 1秒 1秒 1秒 10 10 10 10 每个测试点分值 10 10 10 10 比较方式 全文比较 全文比较 全文比较 全文比较 传统 传统 传统 传统 isbn.pas seat.pas ball.pas drawing.pas 对于C语言 isbn.c seat.c ball.c drawing.c 对于C++语言 isbn.cpp seat.cpp ball.cpp drawing.cpp 三.编译命令（不包含任何优化开关） 对于pascal语言 fpc isbn.pas fpc seat.pas fpc ball.pas fpc drawing.pas 对于C语言 gcc –o isbn isbn.c gcc –o seat seat.c gcc –o ball ball.c gcc –o drawing drawing.c 对于C++语言 g++ –o isbn isbn.cpp g++ –o seat seat.cpp g++ –o ball ball.cpp g++ –o drawing drawing.cpp 四.运行内存限制 运行内存上限 50M 50M 50M 50M 注意事项： 1、文件名（程序名和输入输出文件名）必须使用小写。 2、C/C++中函数main（）的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU 1.9GHz， 内存512M， 上述时限以此配置为准。 各省在自测时可根据具体配置调整时限。 1.ISBN号码 （isbn.pas/c/cpp）…，9，再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的结果4作为识别码。 你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。 【输入】 输入文件isbn.in只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。 【输出】 输出文件isbn.out共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。 【输入输出样例1】 isbn.in isbn.out 0-670-82162-4 Right 【输入输出样例2】 isbn.in isbn.out 0-670-82162-0 0-670-82162-4 2.排座椅 （seat.pas/c/cpp）D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列 的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。 请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。 【输入】 输入文件seat.in的第一行，有5各用空格隔开的整数，分别是M，N，K，L，D（2=N，M=1000，0=KM，0=LN，D=2000）。 接下来D行，每行有4个用空格隔开的整数，第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。 输入数据保证最优方案的唯一性。 【输出】 输出文件seat.out共两行。 第一行包含K个整数，a1a2……aK，表示第a1行和a1+1行之间、第a2行和第a2+1行之间、…、第aK行和第aK+1行之间要开辟通道，其中ai ai+1，每两个整数之间用空格隔开（行尾没有空格）。 第二行包含L个整数，b1b2……bk，表示第b1列和b1+1列之间、第b2列和第b2+1列之间、…、第bL列和第bL+1列之间要开辟通道，其中bi bi+1，每两个整数之间用空格隔开（行尾没有空格）。 【输入输出样例】 seat.in seat.out 4 5 1 2 3 4 2 4 3 2 3 3 3 2 5 2 4 2 2