**********************************************************************
黄金题目
**********************************************************************
共六道题(编号1-6)
********************************************************************** 问题1:接苹果 [Hal Bursh,2004] 很少有人知道奶牛爱吃苹果。农夫约翰的农场上有两棵苹果树(编号为1和2),
每一棵树上都长满了苹果。奶牛贝茜无法摘下树上的苹果,所以她只能等待苹果
从树上落下。但是,由于苹果掉到地上会摔烂,贝茜必须在半空中接住苹果(没
有人爱吃摔烂的苹果)。贝茜吃东西很快,所以她接到苹果后仅用几秒钟就能吃
完。 每一分钟,两棵苹果树其中的一棵会掉落一个苹果。贝茜已经过了足够的训练,
只要站在树下就一定能接住这棵树上掉落的苹果。同时,贝茜能够在两棵树之间
快速移动(移动时间远少于1分钟),因此当苹果掉落时,她必定站在两棵树其
中的一棵下面。此外,奶牛不愿意不停地往返于两棵树之间,因此会错过一些苹
果。 苹果每分钟掉落一个,共T(1<=T<=1000)分钟,贝茜最多愿意移动W(1<=W<=30)
次。现给出每分钟掉落苹果的树的编号,要求判定贝茜能够接住的最多苹果数。
开始时贝茜在1号树下。 分值:500 问题名称:bcatch 输入格式: *第1行:由空格隔开的两个整数:T和W *第2..T+1行:1或2(每分钟掉落苹果的树的编号) 样例输入(文件名:bcatch.in): 7 2
2
1
1
2
2
1
1 说明: 7分钟内共掉落7个苹果——第1个从第2棵树上掉落,接下来的2个苹果从第1棵树
上掉落,再接下来的2个从第2棵树上掉落,最后2个从第1棵树上掉落。 输出格式: *第一行:在贝茜移动次数不超过W的前提下她能接到的最多苹果数 样例输出(文件名:bcatch.out): 6 说明: 贝茜不移动直到接到从第1棵树上掉落的两个苹果,然后移动到第2棵树下,直到
接到从第2棵树上掉落的两个苹果,最后移动到第1棵树下,接住最后两个从第1
棵树上掉落的苹果。这样贝茜共接住6个苹果。 ********************************************************************** 问题2:数池塘 [Hal Burch and Rob Kolstad, 2004] 农夫约翰的农场可以表示成N*M(1<=N<=100,1<=M<=100)个方格组成的矩形。由
于近日的降雨,在约翰农场上的不同地方形成了池塘。每一个方格或者有积水(
'W')或者没有积水('.')。农夫约翰打算数出他的农场上共形成了多少池塘。
一个池塘是一系列相连的有积水的方格,每一个方格周围的八个方格都被认为是
与这个方格相连的。 现给出约翰农场的图样,要求输出农场上的池塘数。 分值:100 问题名称:lkcount 输入格式: *第1行:由空格隔开的两个整数:N和M *第2..N+1行:每行M个字符代表约翰农场的一排方格的状态。每个字符或者是'W'
或者是'.',字符之间没有空格。 样例输入(文件名:lkcount.in): 10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W. 输出格式: *第1行:约翰农场上的池塘数 样例输出(文件名:lkcount.out): 3 说明: 共有3个池塘:一个在左上角,一个在左下角,还有一个沿着右边界 ********************************************************************** 问题3:带奶牛回家 [Hal Burch, 2004] 贝茜在谷仓外的农场上,她想回到谷仓,在第二天早晨农夫约翰叫她起来挤奶之
前尽可能多地睡上一觉。由于需要睡个好觉,贝茜必须尽快回到谷仓。 农夫约翰的农场上有N(2<=N<=1000)个路标,每一个路标都有唯一的编号
(1..N)。路标1是谷仓,路标N是贝茜一整天呆在那里的果树园。农场的所有路
标之间共有T(1<=T<=2000)条不同长度的供奶牛走的有向小路。贝茜对她识别
方向的能力不是很自信,所以她每次总是从一条小路的头走到尾,再以这条路的
尾作为下一条路的头开始走。 现给出所有路标之间的小路,要求输出贝茜回到谷仓的最短路程(每组输入数据
都保证有解)。 分值:100 问题名称:cowhome 输入格式: *第1行:2个整数:T和N *第2..T+1行:每行用空格隔开的三个整数描述一条小路。前两个整数是这条小
路的尾和头,第三个整数是这条小路的长度(不大于100) 样例输入(文件名:cowhome.in): 5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100 说明: 共有5个路标。 输出格式: *第1行:一个整数,表示贝茜从路标N到路标1所经过的最短路程 样例输出(文件名:cowhome.out): 90 说明: 贝茜可以依次经过路标4,3,2,1到家。 ********************************************************************** 问题4:谁在正中间 [Kolstad, 2004] 农夫约翰为了找到最“中间”的奶牛,正在调查他的牛群。一半奶牛的产奶量不
多于这只“中间”奶牛,另一半的产奶量不少于这只“中间”奶牛。约翰想知道
这只“中间”奶牛的产奶量是多少。 现给出一个奇数N(1<=N<=10000)表示奶牛总数和她们的产奶量(1..1000000)
,要求找出“中间”产量。 分值:50 问题名称:middle 输入格式: *第1行:一个整数N *第2..N+1行:每行包含一个整数,表示其中一只奶牛的产奶量 样例输入(文件名:middle.in): 5
2
4
1
3
5 说明: 五只奶牛和每一只的产量。 输出格式: *第1行:表示“中间”产量的一个整数 样例输出(文件名:middle.out): 3 说明: 1和2不大于3,4和5不小于3。 ********************************************************************** 问题5:公牛数学 [Kolstad, 2004] 公牛在数学方面比奶牛强很多,他们自称可以计算很大的整数之间的乘法,并得
到精确的结果。农夫约翰想知道他们的答案是否正确。请你帮助他检查公牛的答
案。读入2个正整数(不大于1040),计算他们的乘积,输出一个自然数(不能
含有多余的零)。 约翰农夫让你自己做这个工作,不能使用现成的函数。 分值:50 问题名称:bullmath 输入格式: *第1..2行:每行包含一个十进制数 样例输入(文件名:bullmath.in): 11111111111111
1111111111 输出格式: *第1行:读入的两个数的正确的乘积 样例输出(文件名:bullmath.out): 123456789011110987654321 ********************************************************************** 问题6:银行利息 [Kolstad, 2004] 农夫约翰去年赚了一笔钱!他要把这些钱存入银行,但他想知道他能赚多少钱。
他知道银行的年利率R(0到20之间的整数)和他要存钱的年数(0..400)。已知
每年末的本息和作为下一年的本金续存,请你帮助他计算到期时能赚多少钱。输
出本息和的整数部分(不进行四舍五入)。测试数据的输出结果保证在32位数内。 分值:50 问题名称:bankint 输入格式: *第1行:用空格隔开的三个整数:R,M,Y 样例输入(文件名:bankint.in): 5 5000 4 说明: 年利率5%,本金5000,存期4年。 输出格式: *第1行:一个整数,表示Y年后约翰得到的本息和 样例输出(文件名:bankint.out): 6077 说明: 第一年:1.05*5000=5250
第二年:1.05*5250=5512.5
第三年:1.05*5512.5=5788.125
第四年:1.05*5788.125=6077.53125
6077.53125不进行四舍五入的整数部分是6077 ********************************************************************** [em02] |