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

2007衢州一中校庆 noip练习

阿猫的实验

(cat.pas/c/cpp)

【问题描述】

阿猫很喜欢生物学。他还在今年的全国中学生生物学联赛中获得了一等奖。 一天，阿猫在实验室听说了这样一种繁殖能力很强的老鼠。

这种老鼠在出生后的第一个月，可以生出a 对老鼠；第二个月，可以生出b 对老鼠；第三个 月及以后的每个月，都可以生出c 对老鼠。

阿猫对此十分好奇。他很想知道，如果他有一对刚出生的老鼠，按最理想的模式繁殖，且老 鼠不死，那么最少需要多少个月它们就可以覆盖整个地球。

为了完成这一猜想，阿猫需要知道这种老鼠在第N 个月时的数量。

【输入文件】

输入文件cat.in 只有一行，四个数，分别为a，b，c，N（0

【输出文件】

输出文件cat.out 只有一个数，为第N 个月老鼠的数量。

【输入样例】

0 1 1 11

【输出样例】

144

倒金字塔

(purple.pas/c/cpp)

【问题描述】

Purple 国的一支科学考察队到达了举世闻名的古埃及金字塔。

关于金字塔的建造一直是一个未解之谜, 有着“西方史学之父”之称的希罗多德认为，金字塔的

建造是人力和牲畜，花费20 年时间从西奈半岛挖掘天然的石头运送到埃及堆砌而成。也有不少人认为是外星人修建的。人们发现胡夫金字塔的经线把地球分成东、西两个半球，它们的陆地面积是相等的，这种“巧合”大概是外星人选择金字塔建造地点的用意。法国化学家戴维·杜维斯则认为，建造金字塔的巨石不是天然的，而是人工浇筑的。

Purple 国科考队的队员们正准备研究戴维·杜维斯提出的假说。为了研究这种假说，他们需 要用到“倒金字塔模型”。所谓倒金字塔模型，即金字塔由N 层人工浇筑的巨石堆砌而成，非底层

的任意一层巨石的长度和宽度都必须要小于等于它下面的一层巨石的长度和宽度。

现在，科考队队员们打算用手里仅有N 块木板去模拟这个倒金字塔模型。请计算出科考队队 员们能够构建的倒金字塔模型的最大高度。

【输入文件】

输入文件purple.in 的第1 行，为一个正整数N(N

接下来N 行，每行两个数:a，b(a,b

【输出文件】

输出文件purple.out 只有一个正整数，为最多可以堆叠的倒金字塔的高度。所有的木板厚 度均为1。

【输入样例】

3

3 2

1 1

2 2

【输出样例】

3

打地鼠

yy.pas/c/cpp yy.in/out

SDyy喜欢游戏。实际上，YY所喜欢的游戏都是很幼稚的。他幼稚地找到你，让你帮他玩这个游戏。YY的游戏名字叫打地鼠。规则很简单。有一个5*5的棋盘，棋盘外边是高速公路，用绿色表示。如果两个格子拥有公共边，这2个格子就是相邻的。左下角的棋盘格为(1,1)，右上角为(5,5)

游戏开始，在第1秒钟初，YY随便找了一个格子跳了进去，每当秒针跳一下，YY可

以在瞬间完成以下的一种任务：

（1） 什么也不干

（2） 从某个格子移动到相邻的格子

（3） 从某个最外层的格子移动到高速公路上

（4） 从高速公路上移动到某个最外层的格子。

但是，高速公路的管理部门告诉YY，他在任意连续3s内，至多能使用高速公路1s。 在某些秒钟，某些格子上会出现可爱的小动物，比如鼠之类的，如果在这一秒钟，YY恰巧也在这个格子里，设坐标为(x,y)那么他就可以得到1分。分数是累加的。

已知游戏在第M秒末结束，请帮助YY设计一个路线，使得YY可以获得最大的得分，当然为了你的方便，你只需要计算出这个最大得分就可以了。

【输入文件】 yy.in

第一行N：鼹鼠出现的次数。M：游戏的总时间

以下N行，每行包括4个整数，A B C D（1

【输出文件】 yy.out

一个整数，即最高分数

【样例输入】

2 10

1 1 1 5

4 4 8 8

【样例输出】

6

【对样例的说明】

在第6s跑到公路上，第7s跑到（5，4），第8s跑到（4，4）

【数据范围】

对于30%的数据，M

对于100%的数据，M

工作（Work.pas/exe）

【题目描述】

这次故事的主角是HG！转眼4年过去了，HG本科毕业了，于是找了份工作。每天HG会收到一份任务清单，清单上列出了n个可能需要他完成的任务。每个任务包含3个信息：Ti、Ai、Bi，Ti表示完成此任务需要的时间，Ai表示此任务的到达时间，Bi表示此任务的最晚完成时间。在某一时刻若HG手上没有任务，那么他可以选择一个已经到达且还能够在Bi时刻之前（或者恰好在Bi时刻）完成的任务来做。

由于HG有点懒（纯属虚构:D），他想尽量少的减少他的总工作时间，但是他不能在可以做任务的时候故意不做（这样会被炒鱿鱼的>_

你的任务就是求出HG的最少工作时间（即总共有多少时间HG在做任务）。

【输入】

第一行一个整数n表示任务数。

以下n行，每行三个整数Ti,Ai,Bi。（n=1）

【输出】

输出仅一个数，即最少工作时间。

【样例输入】

3

15 0 25

50 0 90

45 15 70

【样例输出】

50

【数据范围】

Ti>=1，0

30%的数据满足n

60％的数据满足n

100％的数据满足n

【说明】

输入数据保证Bi-Ai要大于等于Ti，且小于2Ti。

又上锁妖塔

(tower.in/tower.out)

[题目描述]

小D在X星买完了想要的东西,在飞往下一个目的地的途中,正无聊的他转头看了看身边的小A,发现小A正在玩,可是小A很奇怪,他一直在锁妖塔的周围转来转去,可是就是不进去,于是小D问他:”你在干什么?怎么不上去?”小A说:”我在想怎么从锁妖塔外面爬上去”(倒…) 锁妖塔的建造很特别,塔总共有n层,但是高度却不相同,这造成了小A爬过每层的时间也不同.小A会用仙术,每用一次可以让他向上跳一层或两层,但是每次跳跃后小A都将用完灵力,必须爬过至少一层才能再次跳跃(你可以认为小A需要跳两次一层才休息),小A想用最短的时间爬到塔顶,可是他不能找到时间最短的方案,所以请你帮他找到一个时间最短的方案让他爬到塔顶,小A只关心时间,所以你只要告诉他最短时间是多少就可以了.你可以最后跳到塔外即超过塔高.

[输入格式]

第一行一个数n (n

接下来的n行每行一个数(

[输出格式]

一个数,表示最短时间

[样例输入]

5

3

5

1

8

4

[样例输出]

1

[数据规模]

对20%的数据,n

对40%的数据,n

对60%的数据,n

对100%的数据

,n

(样例说明)