ACM题目、测试用例及参考答案汇编——一次ACM协会内部测试第一题：梦境是虚幻吗？时间限制：3000ms 内存限制：65535KB 难度：★★描述《盗梦空间》是一部精彩的影片，在这部电影里，Cobb等人可以进入梦境之中，梦境里的时间会比现实中的时间过得快得多，这里假设现实中的3分钟，在梦里就是1小时。

然而，Cobb他们利用强效镇静剂，可以从第一层梦境进入第二层梦境，甚至进入三层，四层梦境，每层梦境都会产生同样的时间加速效果。

那么现在给你Cobb在各层梦境中经历的时间，你能算出现实世界过了多长时间吗？比如，Cobb先在第一层梦境待了1个小时，又在第二层梦境里待了1天，之后，返回第一层梦境之后立刻返回了现实。

那么在现实世界里，其实过了396秒（6.6分钟）输入第一行输入一个整数T（0<=T<=100)，表示测试数据的组数。

每组测试数据的第一行是一个数字M(3<=M<=100)随后的M行每行的开头是一个字符串，该字符串如果是"IN" 则Cobb向更深层的梦境出发了，如果是字符串"OUT"则表示Cobb从深层的梦回到了上一层。

如果是首字符串是"STAY"则表示Cobb在该层梦境中停留了一段时间，本行随后将是一个整数S表示在该层停留了S分钟（1<=S<=10000000)。

数据保证在现实世界中，时间过了整数秒。

输出对于每组测试数据，输出现实世界过的时间（以秒为单位）。

样例输入16INSTAY 60INSTAY 1440OUTOUT样例输出396测试输入106INSTAY 60INSTAY 1440OUTOUT6INININOUTOUTOUT7INININSTAY 0 OUTOUTOUT2INSTAY 203INSTAY 0 OUT3INSTAY 10 OUT4INSTAY 10 STAY 10 OUT5INSTAY 20 STAY 20 OUT STAY 120 10INSTAY 20 STAY 20 INSTAY 1440STAY 1440OUTSTAY 120OUTSTAY 11STAY 50测试输出39660306073209723000参考代码：#include<stdio.h>int main(){int n;char a[5];scanf("%d",&n);while(n--){int m,i,b=1,c,time=0;scanf("%d",&m);for(i=0;i<m;i++){scanf("%s",&a);if(a[0]=='I') b*=20;else if(a[0]=='S') {scanf("%d",&c);time+=c*60/b;} else if(a[0]=='O') b/=20;}printf("%d\n",time);}return 0;}第二题：独木舟过河时间限制：3000ms 内存限制：65535KB 难度：★★描述进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。

一条独木舟最多只能乘坐两个人，且乘客的总重量不能超过独木舟的最大承载量。

我们要尽量减少这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟条数。

现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。

根据给出的规则，计算要安置所有旅客必须的最少的独木舟条数，并输出结果。

输入第一行输入s,表示测试数据的组数；每组数据的第一行包括两个整数w，n，80<=w<=200,1<=n<=300，w为一条独木舟的最大承载量,n为人数；接下来的一组数据为每个人的重量（不能大于船的承载量）；输出每组人数所需要的最少独木舟的条数。

样例输入385 65 84 85 80 84 8390 390 45 60100 550 50 90 40 60样例输出533测试输入：2085 65 84 85 80 84 8390 390 45 60100 550 50 90 40 60150 1050 50 90 40 60 5 84 85 80 84112 2050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111150 3050 88 90 78 78 79 84 85 80 84 50 99 86 40 60 5 84 85 80 111 90 96 60 42 2688 98 89 96 99199 5098 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111199 10050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111199 20050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 99 80 111 90 45 60 42 26 99 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111100 199100 245 56100 445 55 46 54199 20050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 99 80 111 90 45 60 42 26 99 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111199 20050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 99 80 111 90 45 60 42 26 99 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111199 20050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 99 80 111 90 45 60 42 26 99 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 2560 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111199 20050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 99 80 111 90 45 60 42 26 99 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111199 20050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 99 80 111 90 45 60 42 26 99 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111199 20050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 99 80 111 90 45 60 42 26 99 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111199 20050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 99 80 111 90 45 60 42 26 99 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111199 20050 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 99 80 111 90 45 60 42 26 99 98 25 34 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 5034 46 50 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 4060 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 4650 50 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111 50 50 90 40 60 584 85 80 84 50 50 90 40 60 5 84 85 80 111 90 45 60 42 26 24 98 25 34 46 5050 90 40 60 5 84 85 80 84 50 50 90 40 60 5 84 85 80 111测试输出：533514222550100122100100100100100100100100参考代码#include <iostream>#include <cstdlib>using namespace std;int compInc(const void *a,const void *b){return *(int *)a - *(int *)b;}int main(){int s;int w,n;cin>> s;int i;int a[300];int j;int sum;int x,y;for(i=0;i<s;i++){sum = 0;cin>> w >> n;for(j=0;j<n;j++){cin>> a[j];}qsort(a,n,sizeof(int),compInc);for(x = 0,y = n-1;x < y; ){if(a[x] + a[y] <= w){x++;y--;}else{y--;}sum++;}if(x == y){sum++;}cout<< sum <<endl;}return 0;}第三题 521521ACM时间限制：1000ms 内存限制：65535KB 难度：★★★描述Acm队的小菜对数学的研究不是很透彻，但是固执的他还是想一头扎进去。