宁波市第27届中小学生计算机程序设计竞赛

小学组复赛试题宁波市第27届中小学生计算机程序设计竞赛复赛试题（小学组）一、题目概览二、提交源程序文件名三、编译命令（不包含任何优化开关）四、运行内存限制运行内存上限128M128M128M128M注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。宁波市计算机学会2012年4月中文题目名称傻瓜电梯数字替换取珠子猜数字输入文件名dianti.inchange.inpearl.inguess.in输出文件名dianti.outchange.outpearl.outguess.out每个测试点时限1秒1秒1秒1秒测试点数目10101010每个测试点分值10101010比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统传统对于pascal语言dianti.paschange.paspearl.pasguess.pas对于C语言dianti.cchange.cpearl.cguess.c对于C++语言dianti.cppchange.cpppearl.cppguess.cpp小学组复赛试题1．傻瓜电梯（dianti.pas/c/cpp）所谓傻瓜电梯指的是在响应用户请求时缺乏相应的“智商”，在上升或下降的过程中不能把中途的乘客捎带入电梯，而只会严格按照用户发出请求的先后顺序依次完成任务。比如，原来电梯在1楼，首先6楼有一位乘客发出请求，要求由6楼乘坐到10楼去，此时电梯马上会上去，但在电梯上升到3楼时，另外一位乘客请求由5楼乘坐到8楼去，傻瓜电梯却不会在上升途中把5楼的乘客捎带上去，而只会先把6楼的乘客送到10楼，然后再下来把5搂的乘客送到8楼。傻瓜电梯由i楼上升到i+1楼（或下降到i-1楼）的时间都是3秒，每到达一个楼层，不管进出乘客有多少，也不管乘客只有进、只有出或者进出电梯都有，所耽搁的时间都是6秒。现在味味要根据傻瓜电梯接受到的n个用户请求，编程计算傻瓜电梯把所有乘客送到目标楼层时总共所需要的时间。如果某批乘客到达目标楼层后，电梯没有马上要响应的请求，则电梯在前一批乘客的目的地等待，这个等待时间也需计入总花费时间。直到下一批乘客发出新请求，电梯才会从当前位置出发，前往下一批乘客的出发楼层。【输入】输入文件dianti.in第一行包含两个整数x（1=x=100）和n（1=n=100），分别表示傻瓜电梯开始所在的楼层和总共接收到的请求数目。下面有n行，每行包含3个整数，依次表示该请求发出的时间、乘客目前所在的楼层和将要去的目标楼层。其中请求发出的时间以秒为时刻单位，最大可能的值是2000。如果某两个请求的发出时间相同，则按照输入文件中原始的先后顺序依次处理。【输出】输出文件dianti.out只包含一行一个整数，表示傻瓜电梯把所有乘客送到目标楼层后总共所需要的时间（从得到第一条请求时开始计算时间），单位是秒。【输入输出样例1】【样例1解释】第一批乘客发出请求到离开电梯所需时间：3*2+6+3*11+6=51从前一批乘客离开电梯到第二批乘客离开电梯所需时间：3*6+6+3*4+6=42第三批乘客从出发地出发到离开电梯所需时间：3*8+6=30（由于出发地与前一批乘客目的地相同，所以上下客时间不必再加6）从前一批乘客离开电梯到第四批乘客离开电梯所需时间：3+6+3*8+6=39总花费时间：51+42+30+39=162【输入输出样例2】宁波市计算机学会2012年4月dianti.indianti.out3410102181921128610162dianti.indianti.out121023305160小学组复赛试题【问题描述】2.数字替换(change.pas/c/cpp)味味很喜欢玩一个数字替换的游戏，数字替换游戏是这样的：给出一个n位正整数a，然后再给你一个长度为m的数字序列b，味味可以用b中的一些数字与a中各个位置上的数字进行一对一的交换（当然也可以选择不交换）。当然b中的每个位置上的数字最多只能被使用一次。这个游戏的目的是经过一系列替换后，使a的数值达到最大。味味很聪明，在位数不多的情况下，总能快速的求出最后a的最大数值，但是当n很大时，味味就无能为力了，所以她希望会写程序的你帮助她快速的求解a最后能到达的那个最大值。【输入】输入文件change.in共包含三行。第一行两个用空格隔开的正整数n，m。第二行一个正整数a（a的最高位必定不是0）。第三行一个长度为m的数字序列b。【输出】输出文件change.out仅包含一行一个数值，表示a最大可能达到的数值（输出不能含前导0）。【输入输出样例1】【输入输出样例1解释】b中的一个1和a中的第二位上的0进行交换。【输入输出样例2】【数据范围】对于20%的数据1≤n，m≤10对于50%的数据1≤n，m≤2000对于100%的数据1≤n，m≤100000宁波市计算机学会2012年4月change.inchange.out4310240101124change.inchange.out36876123459976小学组复赛试题【问题描述】3.取珠子(pearl.pas/c/cpp)味味妈妈有一串珠子串成的项链，这个项链中的珠子最多有3种颜色（红、蓝、白，分别用r、b、w表示）。某天，味味想从妈妈项链中取出一些珠子来玩，妈妈虽然答应了，但提出了以下条件：（1）只能在项链中选择一个地方剪断，然后从断开的两端开始依次取出珠子；（2）每一端取珠子时，如果珠子颜色与该端第一颗珠子颜色相同则可以连续取下去，直到出现一颗与该端第一颗颜色不同的珠子。如果遇到白色珠子则可根据需要看做蓝色或者红色。味味对于颜色并没有特殊要求，但她想得到尽可能多的珠子。为方便表示，我们给项链中的珠子按顺时针方向编号，如图-1和图-2所示为两种可能的项链情况（珠子都有11颗）。对于图-1来说，如果在1和2号珠子之间剪断，则味味可以取到共2颗珠子。而如果在6和7号珠子之间剪断，则味味可以取到共5颗珠子（左边取3颗红色r，右边取2颗蓝色b），而5颗珠子也是味味从这串项链中最多可以取到的珠子数量。对于图-2中的项链来说，如果在1和2号珠子之间剪断，则共可取走4颗珠子（将1号珠子当做蓝色，这样左边可取3颗，右边可取1颗蓝色b）。而如果在2和3号之间剪断，则共可取走6颗珠子（将1号珠子当做蓝色，这样左边可取4颗蓝色b，右边可取2颗红色r）。【输入】输入文件pearl.in共包含二行。第一行一个整数n，表示项链中珠子的总数。第二行为一串长度为n的字符，由字符r，b，w组成。表示项链从某个珠子开始按顺时针方向展开的珠子排列情况（当然，这个珠子并不一定是味味实际需要剪断的位置）。【输出】输出文件pearl.out仅包含一行一个数值，表示按照妈妈的规则，味味最多能得到的珠子数量。【输入输出样例1】【输入输出样例1解释】假设输入字符串中第一个字符表示1号珠子将1号珠子看成蓝色，则在2和3号珠子之间剪断，味味可得到的6颗珠子编号分别为1、2、3、4、10、11；也可在4和5号珠子间剪断，将7号珠子看成蓝色，则味味可得到珠宁波市计算机学会2012年4月pearl.inpearl.out11wbrrbbwbrbb6小学组复赛试题子的编号为3、4、5、6、7、8。【输入输出样例2】【数据范围】对于60%的数据3≤n≤100对于100%的数据3≤n≤350【问题描述】4.猜数字(guess.pas/c/cpp)味味最近在玩猜数字的游戏，现在她也希望你来玩一下这个游戏。猜数字游戏的规则是这样的，告诉你一个正整数n(2=n=11),然后味味心中会想一个n个数字组成的数字串（数字串最前面若干位可能是0）。味味会随意排列n位数上的数字，这样可能产生n！个n位数。(n！=1×2×3×4×5×……×n，n!念作“n阶乘”).比如味味想了一个三位数abc，那么一共会产生六个三位数，分别为abc,acb,bac,bca,cab,cba然后味味会把这n!个n位数求和得到S（若某数第一位开始有若干个0，则求和时这些0舍去。如有数“0123”，则求和时加到s中的值是123），她会告诉你总和S减去她心中想的那个数的值，请你猜出味味心中想的那个数。【输入】输入文件guess.in共包含两行。第一行一个整数n（含义如前面所述），第二行一个正整数S，表示n！个数的总和减去味味心中那个数的值。【输出】输出文件change.out共一行一个数，表示味味心中想的那个n位数(测试数据保证存在唯一解)。如果该数第一位开始有若干个0，则输出时这些0也必须输出（详见样例3）。【输入输出样例1】【输入输出样例1解释】如果味味心中想的是123，则S=123+132+213+231+312+321-123=1209符合要求。【输入输出样例2】宁波市计算机学会2012年4月pearl.inpearl.out11bbbbrbbbbrw6guess.inguess.out31209123小学组复赛试题【输入输出样例2解释】如果味味心中想的是1222，则S=1222+1222+1222+1222+1222+1222+2122+2122+2122+2122+2122+2122+2212+2212+2212+2212+2212+2212++2221+2221+2221+2221+2221+2221-1222=45440符合要求。【输入输出样例3】【输入输出样例3解释】如果味味心中想的是09，则S=09+90-09=9+90-9=90，符合要求。【数据范围】对于20%的数据n≤3对于60%的数据n≤5对于100%的数据2≤n≤11，0≤S≤10宁波市计算机学会2012年4月guess.inguess.out4454401222guess.inguess.out2900918