信息学奥林匹克竞赛复赛试题

20072007衢州一中校庆衢州一中校庆 noip noip练习练习 第一题第一题阿猫的实验（cat.pas cat.pas） 第二题第二题倒金字塔（purple.pas purple.pas） 第三题第三题打地鼠（yy.pas ） 第四题第四题工作（Work.pas/） 第五题第五题又上锁妖塔（tower） 阿猫的实验 (cat.pas/c/cpp)(cat.pas/c/cpp) 【问题描述】 阿猫很喜欢生物学。他还在今年的全国中学生生物学联赛中获得了一等奖。 一天，阿猫在实验室听说了这样一种繁殖能力很强的老鼠。 这种老鼠在出生后的第一个月，可以生出a 对老鼠；第二个月，可以生出b 对老鼠；第三个 月及以后的每个月，都可以生出c 对老鼠。 阿猫对此十分好奇。他很想知道，如果他有一对刚出生的老鼠，按最理想的模式繁殖，且老 鼠不死，那么最少需要多少个月它们就可以覆盖整个地球。 为了完成这一猜想，阿猫需要知道这种老鼠在第N 个月时的数量。 【输入文件】 输入文件cat.in 只有一行，四个数，分别为a，b，c，N（0=1，0=Ai,Bi=1200； 30%的数据满足 n=5； 60％的数据满足 n=500； 100％的数据满足 n=1000。 【说明】 输入数据保证 Bi-Ai 要大于等于 Ti，且小于 2Ti。 又上锁妖塔又上锁妖塔 (tower.in/tower.out) [题目描述] 小 D 在 X 星买完了想要的东西,在飞往下一个目的地的途中,正无聊的他转头看了看身边的 小A,发现小A正在玩,可是小A很奇怪,他一直在锁妖塔的周围转来转去,可是就是不进去, 于是小 D 问他:”你在干什么?怎么不上去?”小 A 说:”我在想怎么从锁妖塔外面爬上去”(倒…) 锁 妖塔的建造很特别,塔总共有 n 层,但是高度却不相同,这造成了小 A 爬过每层的时间也不同.小 A 会用仙术,每用一次可以让他向上跳一层或两层,但是每次跳跃后小 A 都将用完灵力,必须爬过至 少一层才能再次跳跃(你可以认为小 A 需要跳两次一层才休息),小 A 想用最短的时间爬到塔顶, 可是他不能找到时间最短的方案,所以请你帮他找到一个时间最短的方案让他爬到塔顶,小 A 只 关心时间,所以你只要告诉他最短时间是多少就可以了.你可以最后跳到塔外即超过塔高. [输入格式] 第一行一个数 n (n=10000),表示塔的层数. 接下来的 n 行每行一个数(=100),表示从下往上每层的高度. [输出格式] 一个数,表示最短时间 [样例输入] 5 3 5 1 8 4 [样例输出] 1 [数据规模] 对 20%的数据,n=10 对 40%的数据,n=100 对 60%的数据,n=5000 对 100%的数据,n=10000 (样例说明) 5771001803090012095 579036822859633082 5771001803090012386 576137399735760696 5771001803090013594 578077579902515512 5771001803090012387 577164982601818051 5771001803090012138 572131192158918326 5771001803090012359 579036822361076053 5771001803090012356 576135286143791742 5771001803090012355 575087869704693279 17088100343355274 101229944325833379 17088100343355275 101866732938832008 17088100343356107 101581152501500522 17088100343356108 101000180059871732 17088100343354295 101074194142687017 17088100343356184 101878660869628802 17088100343356185 101775831174086674 17088100343356109 101086014373572846 17088100343356110 101152207216014916 17088100343355237 101027041605702709 17088100343355238 101229364861425414 17088100343356169 101862204402635718 17088100343354928 101760654089788804