2018年常州市编程小能手比赛试题

T1:春游(a.cpp或a.pas)题目描述

小Ｘ就读的CZ中学今年又取得了小高考的空前佳绩，全校师生都很开心，于是大家希望找个地方去春游，在广泛征集了全校师生的意见后，最终决定前往嬉戏谷游玩一天。出行方案为租用大巴，可供租用的大巴有两种，一种是49座的，一种是33座的，49座的大巴每辆租金为3300元，33座的大巴每辆租金为1900元，全校师生共有n人，现在学校希望找到一种最省钱的租车方案，这个任务学校交给了擅长编程的小Ｘ同学，而小Ｘ同学最近太忙了，他觉得这么简单的任务交给小学生就行了，如果你想参加江苏省“信息与未来”夏令营那就先把这个问题解决了吧！输入输入数据仅有一行包含一个正整数n，表示CZ中学出游的总人数输出输出数据仅有一行包含一个正整数，表示租车所需的最少费用。样例输入67样例输出5200样例解释最省钱的租车方案是两种大巴各租一辆，总费用为5200元，其他的方案均不可能低于该费用。数据范围20%的数据，n<=5040%的数据，n<=10080%的数据，n<=10^6100%的数据，n<=10^12，注意这部份数据要用longlongT2:BMI(c.cpp或c.pas)题目描述小Ｘ经过刻苦训练获得了NOIP的国一，并参加了NOI，获得了保送资格，被保送到南都大学学习，进入大学以后，小Ｘ觉得中学编程太辛苦了，应该好好犒劳一下自己，刚好南都大学周边美食如云，吃不胜吃，小Ｘ不到一个学期就长了30多斤，四年下来已经胖得不成样子，体重一举飙升到了118kg，同时血压也升到了128mmHg，离正常血压的上限也不远了，数字都很吉祥，但身体状况已呈险兆，上个楼梯就心慌气促，于是下定决心要减重，正所谓胖子不是一天就能吃成的，瘦下来也不可能饿几天就达到，小Ｘ的短期目标就是减到像Q老师那么瘦，尽管也从没有人夸过Q老师瘦！当然小Ｘ的最终目标是减到正常体重，正常体重怎么算呢？国际通用的标准是BMI指数，以下科普一下BMI指数：BMI指数=体重/(身高^2)，正常范围在18到24之间，小于18过轻，大于24过重。这里体重的单位为公斤(kg)，身高的单位是米(m)。如费德勒的身高为185厘米，体重为85公斤，其BMI=85/(1.85*1.85)≈24.8356。输入输入数据包含两个用空格隔开的正整数，分别表示身高和体重，身高的单位是厘米(cm)，体重的单位为公斤(kg)，1

米等于100

厘米。输出输出数据第一行为一个字符串，“Good!”表示正常，“Toofat!”表示过重，“Toothin!”表示过轻，双引号不需要输出，感叹号都是英文字符。如果体重正常则不用输出第二行，否则第二行输出一个正整数w，表示此人离正常体重的最小整数差值，假如此人过重，则他要减去w

公斤才能使得BMI

指数小于等于24，如果太轻则要增加w

公斤才能使得BMI

指数大于等于18。样例输入175118样例输出Toofat!45样例输入2

17350

样例输出2

Toothin!

4

样例输入3

17658

样例输出3

Good!

样例解释

样例1为小Ｘ的身高体重，小Ｘ最少需要减掉45公斤体重才能达标；样例二为某大学水的身高体重，

他最少需要增加4公斤体重才达标；样例三是某学佛的身高体重，他的BMI大约等于18.72，正常!

数据范围

20%的数据，BMI在正常范围内

另外80%的数据，一半太胖，一半太瘦

100%的数据，身高<=250，体重<=300T3:人工智能(d.cpp或d.pas)题目描述

人胖了就容易打瞌睡，打瞌睡又会导致长胖，这对小Ｘ的减重计划很不利，于是小Ｘ决定做点动脑子的事来抵御瞌睡虫的进袭，小Ｘ决定响应国务院的号召投身到人工智能的研究开发大潮中去，具体研究什么好呢？小Ｘ再三思考后决定开发国际象棋的人工智能软件，虽然国际象棋的软件已经能够战胜人类世界冠军了，但那是基于搜索的AI(AI是人工智能的简称)，小Ｘ想写一个基于机器学习的国际象棋AI，目标是战胜IBM的深蓝，小Ｘ的国际象棋水平也不差，曾获得过市青少年比赛的冠军，机器学习顾名思义就是让机器像人一样学习，小Ｘ首先训练机器学习棋子对棋盘的控制，具体做法是小Ｘ先在棋盘上放置若干个车和后，然后让机器判断有多少个格子没有被车和后控制到。车和后的吃子规则如下：车：横、竖均可以走，步数不受限制，但不能斜着走。后：横、竖、斜都可以走，步数不受限制。无论是车还是后都不能越过棋子去吃子，用作训练的国际象棋棋盘可以放大缩小，并不限于8×8的棋盘，车和后所在的位置当然是被控制的，它们能走到的位置也都被控制。输入第一行包含一个正整数n，表示棋盘的大小接下来n行，每行n个整数，其中0表示棋盘上这个格子为空的，1表示为车，2表示为后样例输入输出一行一个整数，表示没有被控制到的格子数量

样例输入50000001010002000101000000样例输出4样例解释

红色格子为样例中被控制到的格子，中间那个后能够斜着走到四个角落的格子(图中白色的格子)，但

因受到四个车的阻隔而不能控制到那四个格子！

数据范围

20%的数据，保证棋盘上只有车

50%的数据，n<=50

80%的数据，n<=200

100%的数据，n<=1000，车的数量<=n*n，后的数量<=nT4:基因锁(e.cpp或e.pas)题目描述小Ｘ终于意识到需要花大力气减重了，他询问了若干个减重专家后决定采用最适合年轻人的运动减重方案，考虑再三，小Ｘ最终选择了打羽毛球的方式，一个原因是小Ｘ的小伙伴大都喜欢打羽毛球，其次是打羽毛球要抬头，对活动颈椎有好处，刚好可以缓冲编程久了对颈椎的压迫。经过一个月的努力，小Ｘ的国际象棋AI在机器学习的环境中进步神速，已经能够轻松战胜深蓝了，但小Ｘ的体重却没有太大变化，离第一目标Q老师尚有一段距离，这天小Ｘ跟往常一样白天打羽毛球，晚上训练AI后就睡觉了，睡梦中小Ｘ梦见自己先是被一束强光罩住了，随后被吸进了UFO，落到了UFO的甲板上，只见一只会说人话的机器狗迎上前来，对小Ｘ说：“小Ｘ先生好，我家主人在会客舱等你多时了！”随后小Ｘ被带到了一位长了三只眼的外星首领面前。外星首领很友善地和小Ｘ握了手，然后对小Ｘ说：“你做的AI非常棒，我已经很多年未遇对手了，今天跟你的AI打得旗鼓相当，十分过瘾，这次请你来作客是想和你交个朋友，你有什么要求尽管提，我们会尽量满足！”小Ｘ听罢受宠若惊，心想外星科技这么发达，也许有办法让我立刻变得像中天学长一样帅！于是小Ｘ提出了这个超高难度的要求，外星首领听后微微一笑：“你这个要求可以满足，但我们要对你的基因进行一次分析，把你基因中的肥胖基因找出来，然后给它们加上锁！象我们熟知的那样，人类的基因序列(英文缩写为DNA)是一个由字母'A','C','G','T'组成的字符串，肥胖基因是其中的一个子串(子串为原串中一段连续的字符)，外星人对小Ｘ的基因手术过程是这样的：先找出所有的肥胖基因，并将它们用基因墨水染成红色，然后将某些字符加上基因锁，一把基因锁只能锁住一个字符，一个肥胖基因只要有一个字符加上了基因锁，则这个肥胖基因就不再起作用，现在要你计算有多少个字符被基因墨水染成了红色？最少需要多少把基因锁才能将所有的肥胖基因锁住？输入第一行包含两个用空格隔开的正整数L1，L2，表示小Ｘ基因的长度和肥胖基因的长度。第二行为一个长度为L1的字符串，表示小Ｘ的基因。第三行为一个长度为L2的字符串，表示肥胖基因。数据保证L1>L2。输出输出一行包含两个整数，表示被基因墨水染成了红色的字符个数和所需的基因锁数量，两数之间严格

用一个空格隔开。样例输入163CGCGCATCGCATTAGGCGC6，肥胖基因长度不超过10，保证字符只会出现'A','C','G','T'样例输出82样例解释

红色字符为被基因墨水染成红色的全部3个肥胖基因，总共有8个字符；只需2把基因锁就可以把所

有的肥胖基因(CGC)锁住。分别锁住第3个字符‘C’和第9个字符‘G’即可。注意第一个和第二个肥胖

基因有重叠，给第三个字符‘C’加上锁就同时将两个肥胖基因锁住了。

数据范围

10%的数据，肥胖基因为单个字符

40%的数据，所有的肥胖基因互相不重叠

100%的数据，基因长度不超过106T5:量子计算(f.cpp或f.pas)题目描述

做完基因锁手术后，小Ｘ又被机器狗带回到了会客舱，外星首领请小Ｘ喝了杯龙冠龙井，说道：“此茶乃G20峰会专用，对你的术后恢复大有裨益，在送你回地球之前，你可以再问一个问题。”小Ｘ问道：“人类这么多年都未能破译基因密码，你们是如何做到的呢？”外星首领答道：“这全靠我们的科学家发明的128位量子计算机，它的计算速度大约是2的128次方，而地球上最快的光电计算机目前最快能算到2的32次方左右。”小Ｘ梦醒之后上网查阅了一下有关量子计算机的最新发展状况，发现米国已经在研制50位的量子计算机了，联想到最近发生的中兴事件，小Ｘ心想一旦量子计算技术再受制于人，那后果就十分严重了，于是小Ｘ计划研制64位的量子计算机，他觉得这个任务有些艰巨，需要找几位天资聪颖且志同道合的小伙伴来帮助自己，于是就想到了这次的程序设计小能手比赛，小Ｘ出了下面这个题目来考考小朋友们，通过的同学将有机会跟小Ｘ一起研制量子计算机哦！一个圆被均分成了n个区域，现有m种可供选择的颜色给图中的区域涂色，每一个区域只能涂一种颜色，且相邻的区域要涂不同的颜色，问有多少种不同的涂色方式？由于结果很大，你只要输出结果除以10000007的余数的值。以下是n=5的时候的圆被分成的样子。输入输入数据仅有一行包含两个用空格隔开的正整数n,m，即圆被分成了n个区域，有m种可供选择的颜色。输出输出数据仅有一行包含一个整数，表示不同的涂色方式，请输出对10000007

求余后的值。样例输入53样例输出30数据范围10%的数据m=240%的数据m<=3，n<=1570%的数据m<=5，n<=100100%的数据m<=100，n<=1000T6:拔河(g.cpp或g.pas)题目描述

龙城八大高校校友联盟继西太湖义行之后又隆重推出了拔河比赛，小Ｘ所在的南都大学校友会对这项赛事十分重视，专门指定重量级的小Ｘ来负责此事，每天下班后南都大学校友会的拔河队员只要有空都会前往中天体育馆训练，训练前小Ｘ先要将所有队员分成两个队，每队人数最多只能相差1人，且重量要尽可能接近，小Ｘ最近忙于研制量子计算机，没空写这个拔河程序，于是他找到了你，希望你帮他完成这项任务。输入输入数据第一行包含一个正整数n，表示人数第二行包含n

个用空格隔开的正整数，表示每个人的重量ai输出输出一行若干个整数，其中第一个整数为该组人数t，之后t

个整数表示每个人在原始数据中的编号，相邻两个整数间用一个空格隔开(其中一组的人确定下来后，另一组自然而然也就确定下来了)，你只要输出任意一种可行的方案。样例输入6533334样例输出3123样例解释1,2,3

号为1

组，体重总和为5+3+3=11，另外三个人为另一组，体重总和为10，相差最小。数据范围40%的数据，N<=6，ai<=1070%的数据，N<=24，ai<=500100%的数据，N<=36，ai<=1015，注意重量要用longlong

类型数据！T7:买衣服(h.cpp或h.pas)题目描述

不知道是拔河训练的作用还是那个梦的缘故，反正小Ｘ是一天天瘦下来了，虽然还没有中天学长那么帅，但比起Q老师已经瘦了很多，小Ｘ原先买的衣服都嫌大了，于是他想去买些新衣服，小Ｘ的衣服原先一直是在非主流服装店买的，他的衣服一般店里是买不到的，而去非主流服装店肯定能买到，如膝盖上挖了两个洞的牛仔裤，正常人穿了像雨衣的冲锋衣等应有尽有，并且每买一件就送一张优惠券，小Ｘ这些年下来积聚了好多张优惠券，这次非主流服装店恰好举行优惠活动，用优惠券购买衣服可享受优惠价！小Ｘ来到了非主流服装店，他看上了n件衣服，每一件衣服价格为Pi，小Ｘ现在手中共有m个单位的现金，以及k张优惠卷。小Ｘ可以在购买某件衣服时，使用至多一张优惠券，若使用优惠券，则该衣服的价格会下降至Qi，小Ｘ想知道他最多可以买几件衣服。输入第一行包含三个用空格隔开的正整数n,k,m，依次表示衣服总数和优惠券数量及现金总数。接下来n

行每行包含两个整数Pi,Qi，表示该件衣