2006ACM杯比赛往年试题集锦.docVIP

A: Pell数列 time limit: 3000ms Memory limit: 65536kB Submissions: 1227 Accepted: 379 题目描述 Pell数列a1, a2, a3, ...的定义是这样的，a1 = 1, a2 = 2, ... , an = 2 * an ? 1 + an - 2 (n 2)。给出一个正整数k，要求Pell数列的第k项模上32767是多少。 输入 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k 1000000)。 输出 n行，每行输出对应一个输入。输出应是一个非负整数。 样例输入 2 1 8 样例输出 1 408 Global No. B: 二叉树 time limit: 3000ms Memory limit: 65536kB Submissions: 1537 Accepted: 268 题目描述 如上图所示，由正整数1，2，3……组成了一颗二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。 输入 输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 = m = n = 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。 输出 对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。 样例输入 3 12 0 0 样例输出 4 Global No. C: 金银岛 time limit: 3000ms Memory limit: 65536kB Submissions: 933 Accepted: 188 题目描述 某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类, 每种金属重量不同，分别为n1, n2, ... , ns，同时每个种类的金属总的价值也不同，分别为v1,v2, ..., vs。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。 输入 第1行是测试数据的组数k，后面跟着k组输入。每组测试数据占3行，第1行是一个正整数w (1 = w = 10000)，表示口袋承重上限。第2行是一个正整数s (1 = s =100)，表示金属种类。第3行有2s个正整数，分别为n1, v1, n2, v2, ... , ns, vs分别为第一种，第二种，...，第s种金属的总重量和总价值(1 = ni = 10000, 1 = vi = 10000)。 输出 k行，每行输出对应一个输入。输出应精确到小数点后2位。 样例输入 2 50 4 10 100 50 30 7 34 87 100 10000 5 1 43 43 323 35 45 43 54 87 43 样例输出 171.93 508.00 Global No. D: 集合加法 time limit: 3000ms Memory limit: 65536kB Submissions: 622 Accepted: 381 题目描述 给出2个正整数集合A = {pi | 1 = i = a}，B = {qj | 1 = j = b}和一个正整数s。问题是：使得pi + qj = s的不同的(i, j)对有多少个。 输入 第1行是测试数据的组数n，后面跟着n组测试数据。每组测试数据占5行，第1行是和s (1 = s = 10000)，第2行是一个正整数a (1 = a = 10000)，表示A中元素的数目。第3行是a个正整数，每个正整数不超过10000，表示A中的元素。第4行是一个正整数b (1 = b = 10000)，表示B中元素的数目。第5行是b个正整数，每个正整数不超过10000，表示B中的元素。注意：这里的集合和数学书上定义的集合有一点点区别——集合内可能包含相等的正整数。 输出 n行，每行输出对应一个输入。输出应是一个非负整数。 样例输入 2 99 2 49 49 2 50 50 11 9 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1 样例输出 4 9 Global