程序设计比赛试题.doc

程序设计比赛试题最少钱币数:【问题描述】这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数,一般而言有多种方式。例如:给定了6种钱币面值为2、5、10、20、50、100,用来凑15元,可以用5个2元、1个5元,或者3个5元,或者1个5元、1个10元,等等。显然,最少需要2个钱币才能凑成15元。你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑成某个给出的钱数。【要求】【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M(1<=M<=2000,整数),接着的一行中,第一个整数K(1<=K<=10)表示币种个数,随后是K个互不相同的钱币面值Ki(1<=Ki<=1000)。输入M=0时结束。【数据输出】每个测试用例输出一行,即凑成钱数值M最少需要的钱币个数。如果凑钱失败,输出“Impossible”。你可以假设,每种待凑钱币的数量是无限多的。【样例输入】156251020501001120【样例输出】2ImpossibleFeli的生日礼物【问题描述】Felicia的生日是11月1日(和Kitty是同一天生的哦)。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli,不过她说,这份礼物可不是白送的。Feli要帮她一个忙,才能够得到心仪已久的玩具。Kitty说,“Kitty猫”玩具已经卖出了n!个,n<=10^100*_*,Kitty想知道确切的数字,而不是无聊的“一个数加个感叹号”。Feli听了大吃一惊。要知道,算出n!是一个无比艰巨的任务。Feli告诉Kitty,就算Feli算出n!,Kitty也看不下去,因为当n=20时,计算机的长整型已经存不下了(Kitty只能接受1-9之间的数字)。于是Kitty说,你只要告诉我n!最后一位非0的数就可以了。Feli想了想,立刻动手写了个程序算出了正确的答案。现在,请你也试试看!注意哦,AC的男生将会得到一个“HelloKitty”计算器(可编程,CPU1THz,Mem1TMB),AC的女生将会得到一个仿真“HelloKitty”宠物(善解人意,无须喂养,智商1101,附带写情书功能)。【要求】【数据输入】每行一个n,直到输入数据结束【数据输出】对应输入的n,每行输出一个答案【样例输入】1101【样例输出】8蛇行矩阵【问题描述】蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。【要求】【数据输入】本题有多组数据,每组数据由一个正整数N组成。(N不大于100)【数据输出】对于每一组数据,输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。【样例输入】5【样例输出】1361015259**********青蛙的约会【问题描述】两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。【要求】【数据输入】输入只包括一行5个整数x,y,m,n,L,其中x≠y<,0<m、n<,0<L<。【数据输出】输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"【样例输入】12345【样例输出】4敲七【问题描述】输出7和7的倍数,还有包含7的数字例如(17,27,37...70,71,72,73...)【要求】【数据输入】一个整数N。(N不大于30000)【数据输出】从小到大排列的不大于N的与7有关的数字,每行一个。【样例输入】20【样例输出】71417连续邮资问题【问题描述】G国发行了n种不同面值的邮票,并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,使得可在1张信封上贴出从邮资1开始,增量为1的最大连续邮资区间。例如,当n=5和m=4时,面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。编程任务:对于给定的正整数m和n