信息奥赛测试题 (2)

《信息奥赛测试题 (2)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2007年山东省信息学奥林匹克夏令营提高班测试题说明:1.提高一班的同学完成第1、2、3、5题；2.提高二班的同学完成第1、4、5、6题；3.把四个题目的源程序放在一个文件夹(以“姓名＋学校”命名)下提交，所有题目的内存限制为2M，时限为1S。1.数制转换(jinzhi)【题目描述：】有一种R数制的基数是3，权值可以取-1，0，1，并且分别用符号-，0，1表示。这种R进制和十进制可以相互转化：如：R进制十进制10110（1*32+0*31+1*30=10）-0-3（-1*31+0*30）-1-2（-1*31+1*30）编程要求

2、：输入十进制数n，输出n的R进制数，要求前面不能有多余的0，如：十进制数10的R进制数表示成：101，不能写成0101。【输入】：(jinzhi.in)十进制数N，范围：-109<=N<=109。【输出】：(jinzhi.out)一行数，N的R进制表示。中间不能有多余的空格。【样例输入】：10【样例输出】：1012.合并石子(stone)【问题描述：】小Ray在河边玩耍，无意中发现一些很漂亮的石子堆，于是他决定把这些石子搬回家。河滩上共有n堆石子，小Ray在把石子搬回家之前首先要把这n堆石子合并为一堆石子。已知小Ray每次可以

3、选择其中的两堆石子合并为一堆，合并一次石子他要消耗的体力是两堆石子的数量和。请计算小Ray把n堆石子合并成一堆最少消耗的体力值是多少。【输入：】(stone.in)第一行：n（<=30000）.第二行：那个用空格隔开的数，分别表示n堆石子的数量。【输出：】(stone.out)n堆石子合并成一堆所消耗的最小体力值。【样例输入：】3124【样例输出：】103.产生数（change）【问题描述:】　　给出一个正整数n（n<10^50)和k个变换规则（k<=15）。　　每个变换规则是指：　　　一位数可变换成另一个一位数：规则的右部不

4、能为零。　　例如：n=234。有规则（k＝2）：　　　　2－>5　　　　3－>6　　上面的整数234经过变换后可能产生出的整数为（包括原数）:　　　234　　　534　　　264　　　564　　共4种不同的产生数。【任务：】　　给出一个整数n和k个变换规则。求经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。【输入：】(change.in)第一行：n。第二行：k。以下k行：每行两个一位数：xy，中间一个空格，表示一个变换规则：x可以变为y。【输出：】(change.out)一个整数（满足条件的个数）：【输

5、入样例：】23422536【样例输出：】44.最优时间表问题(table)【问题描述:】一台精密仪器的工作时间为n个时间单位.与仪器工作时间同步进行若干仪器维修程序.一旦启动维修程序,仪器必须进入维修程序.如果只有一个维修程序启动,则必须进入该维修程序.如果在同一时刻有多个维修程序,可任选进入其中的一个维修程序.维修程序必须从头开始,不能中间插入.一个维修程序从第s个时间单位开始,持续t个时间单位,则该维修程序在第s+t-1个时间单位结束.为了提高仪器使用率,希望安排尽可能短的维修时间.编程任务:对于给定的维修程序时间表,编程

6、计算最优时间表.【输入：】(table.in):第1行有2个正整数n和k..n表示仪器的工作时间单位,k是维修程序数.在接下来的k行中,每行有2个表示维修程序的整数s和t,该维修程序从第s个时间单位开始,持续t个时间单位.【输出：】(table.out)一个数,最短维修时间.【输入样例】:15612164118581115【输出样例:】115.商店购物(shopping)【问题描述:】在商店中，每一种商品都有一个价格（用整数表示）。例如,一朵花的价格是2元，而一个花瓶的价格是5元。为了吸引更多的顾客，商店举行了促销活动。促销活

7、动把一个或多个商品组合起来降价销售，例如：三朵花的价格是5元而不是6元，两个花瓶和一朵花的价格是10元而不是12元。编写一个程序，计算顾客购买一定商品的花费，尽量利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。对于上面的商品信息，购买三朵花和两个花瓶的最少花费是：以优惠价购买两个花瓶和一朵花（10元），以原价购买两朵花（4元）。【输入：】(shopping.in):包括一些商店提供的优惠信息，接着是购物清单。第一行优惠商品的种类数（0<=s<=99）。第二行..第s+1行每一行都用几个整数来表示

8、一种优惠方式。第一个整数n（1<=n<=5），表示这种优惠方式由n种商品组成。后面n对整数c和k表示k（1<=k<=5）个编号为c（1<=c<=999）的商品共同构成这种优惠，最后的整数p表示这种优惠的优惠价（1<=p<=9999）。优惠价总是比原价低。第s+2行这一行有一个