信息学奥赛CSP复赛训练题_竞技组_3.pdf

1、Pell数列 Pell数列a1,a2,a3,...的定义是这样的，a1=1,a2 =2,..., an=2 *an − 1 + an- 2(n 2)。 给出一个正整数k，要求Pell数列的第k项模上32767是多少。 时间限制：3000 内存限制：65536 输入 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k(1 ≤ k 1000000)。 输出 n行，每行输出对应一个输入。输出应是一个非负整数。 样例输入 2 1 8 样例输出 1 408 2、苹果和虫子2 你买了一箱n 个苹果，很不幸的是买完时箱子里混进了一条虫子。虫子每x 小时能吃掉一个 苹果，假设虫子在吃完一个苹果之前不会吃另一个，那么经过y 小时你还有多少个完整的苹 果？ 输入 输入仅一行，包括n，x 和y （均为整数）。 输出 输出也仅一行，剩下的苹果个数 样例输入 1049 样例输出 7 3、水下探测器 水下探测器可以潜入湖中在任意水深进行科学探索。湖水的最大深度为 h 米,即它在湖底时 到水面的距离，0=h=100；探测器最初的水下深度为 s 米，0=s=100；当探测器不在水 面（当前深度大于 0）时，每个 u 指令可使它上浮 1 米，而当探测器在水面时，u 指令 是无效的；当探测器不在湖底（当前深度小于 h）时，每个 d 指令可使它下沉 1 米，而 当探测器在湖底时，d 指令是无效的；在执行到无效指令时，探测器不做任何操作而继续执 行下一指令。 编程实现： 根据给定的 h、s 和一个指令序列（由字符 u、d 组成的字符串，长度不超过 100），求出 执行完整的指令序列后，探测器的水下深度。 输入： 第一行：h 和 s，以空格分开。0=s=h=100 第二行：长度不超过 100 的指令字符串，串中仅包含字母 u 或 d 输出： 代表探测器在执行指令后的水下深度的数字。 【样例输入】： 9 1 uduudd 【样例输出】： 2 样例数据分析: 水深9 米,探测器在水下1 米处, 字符u 代表向上1 米,探测器上浮到0 米处 字符d 代表向下1 米,探测器下沉到1 米处 字符u 代表向上1 米,探测器上浮到0 米处 字符u 代表向上1 米,探测器已经在水面,不能上浮,依然在0 米处 字符d 代表向下1 米,探测器下沉到1 米处 字符d 代表向下1 米,探测器下沉到2 米处 最终结果为2 答案： 1、 2、 3、