标题:ACM题集(即时更新)
只看楼主
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
得分:0 

在大家的要求下我找了几个中文的题,其中有些比较简单,难的也有,大家做了在这上面发答案,我给大家去提交

第一题:

防御导弹

Time Limit:1000MS Memory Limit:1000K
Total Submit:93 Accepted:28

Description

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够达到任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在使用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

Input

最多20个整数,分别表示导弹依次飞来的高度(雷达给出高度数据是不大于30000的正整数)

Output

两个整数M和N。表示:这套系统最多能拦截 M 枚导弹,如果要拦截所有导弹最少要配备 N 套这种导弹系统。


Sample Input


300 250 275 252 200 138 245


Sample Output


5 2


第二题:

母牛生小牛

Time Limit:1000MS Memory Limit:1000K
Total Submit:425 Accepted:135

Description

设有一头小母牛,从出生第四年起每年生一头小母牛,按此规律,第N年时有几头母牛?


Input

本题有多组数据。每组数据只有一个整数N,独占一行。(1≤N≤50)


Output

对每组数据,输出一个整数(独占一行)表示第N年时母牛的数量

Sample Input


1
4
5
20


Sample Output


1
2
3
872

第三题:

扬辉三角

Time Limit:1000MS Memory Limit:65536K
Total Submit:461 Accepted:116

Description

输出扬辉三角


Input

本题有测试数据,每组数据仅含一个整数N(N不大于34)。一组数据独占一行。


Output

对于每一组数据,先输出一个

Case #:
。其中#号代表第#组数据。接下来输出一个由数字组成的扬辉三角。一行中的数字之间用一个空格分开。行尾不要有多余的空格。
两组数据之间空开一行。

Sample Input


6
3


Sample Output


Case 1:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Case 2:
1
1 1
1 2 1

第四题:

数素数(注意:数据较大,一般的算法达不到这个效率)

Time Limit:1000MS Memory Limit:65536K
Total Submit:732 Accepted:58

Description

素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2到该数的平方根的素数除它,若有能整除的则该数不是素数。


Input

本题有多组数据,每组数据由两个正整数M,N组成。(0<M<N<1000000)

Output

输出一个整数,表示介于M,N之间(包括M,N)的素数的数量。

Sample Input


5 10
1 3
6 8

Sample Output


2
2
1

第五题:

高精度整数去位去最小问题

Time Limit:1000MS Memory Limit:65536K
Total Submit:154 Accepted:11

Description

键盘输入一个高精度的正整数N,去掉其中任意M个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和M寻找一种方案使得剩下的数字组成的新数最小。输出组成的新的正整数。(不超过240位)

输入数据均不需判错。

如果去掉了某几个位后得到的新整数开头为0,保留0。

Input

本题有多组测试数据,每组测试数据占一行。

一个高精度正整数N(N不超过240位)一个正整数M。(M为不大于N的长度的正整数)

N,M由一个空格分开。

Output

新的正整数,每组数据的输出占一行。不要多余的空白


Sample Input


456547 1
456547 2
456547 3
7773359 2
103 1


Sample Output


45547
4547
447
73359
03


第六题:

行编辑器

Time Limit:10000MS Memory Limit:65536K
Total Submit:129 Accepted:45

Description

一个简单的行编辑程序的功能是:接受用户从终端输入的程序或数据,并存入用户的数据区。

由于用户在终端上进行输入时,不能保证不出差错,因此,若在编辑程序中,“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是,设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据区。允许用户输入出差错,并在发现有误时可以及时更正。例如,当用户发现刚刚键入的一个字符是错的时,可补进一个退格符"#",以表示前一个字符无效;

如果发现当前键入的行内差错较多或难以补救,则可以键入一个退行符"@",以表示当前行中的字符均无效。

如果已经在行首继续输入'#'符号无效。


Input

输入一个多行的字符序列。但行字符总数(包含退格符和退行符)不大于250。


Output

按照上述说明得到的输出。


Sample Input


whli##ilr#e(s#*s)
outcha@putchar(*s=#++);

Sample Output


while(*s)
putchar(*s++);


第七题:


石子归并

Time Limit:1000MS Memory Limit:65536K
Total Submit:55 Accepted:19

Description

你有一堆石头质量分别为W1,W2,W3...WN.(W<=100000)现在需要你将石头合并为两堆,使两堆质量的差为最小。


Input

该程序有多组测试数据,每组测试数据第一行为整数N(1<=N<=20),表示有N堆石子。接下去N行,为每堆石子的质量。


Output

每组测试数据只需输出合并后两堆的质量差的最小值。

Sample Input


5
5
8
13
27
14
2
4
4


Sample Output


3
0

第八题:

青蛙的约会

Time Limit:1000MS Memory Limit:65536K
Total Submit:204 Accepted:17

Description

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。


Input

输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。


Output

输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"


Sample Input


1 2 3 4 5


Sample Output


4




雁无留踪之意,水无取影之心
2007-04-17 10:41
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
得分:0 
这八个有不少做过了.哈哈

2007-04-17 11:23
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
得分:0 
第五题:
变相的整数划分问题.或者也可以用回朔来做.
用一数组把2^i存起来.

倚天照海花无数,流水高山心自知。
2007-04-17 22:57
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
得分:0 
数素数
我数啊数终于没有超过时间了.上次数错了再给看看
想做行编译器却发现没有输入结素标志
#include<stdio.h>
int a[168]={2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,
157,163,167,173,179,181,191,193,
197,199,211,223,227,229,233,239,
241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,
347,349,353,359,367,373,379,383,
389,397,401,409,419,421,431,433,
439,443,449,457,461,463,467,479,
487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,
599,601,607,613,617,619,631,641,
643,647,653,659,661,673,677,683,
691,701,709,719,727,733,739,743,
751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,
859,863,877,881,883,887,907,911,
919,929,937,941,947,953,967,971,
977,983,991,997};
int find(int n)
{
int i;
if(n==1)return 0;
else
{
for(i=0;a[i]<=n&&i<168;i++);
return i;
}
}
int prime(int n)
{
int i;
if(n==1)return 0;
else
{
for(i=0;a[i]*a[i]<=n&&i<168;i++)
{
if(n%a[i]==0)
return 0;
}
return 1;
}
}
void main()
{
int n,m,i,count;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(m<2)
printf("0\n");
else
{
count=0;
if(n<1000&&m<1000)
{
count+=find(m);
count-=find(n);
count+=prime(n);
}
else if(n<=1000&&m>=1000)
{
count=168-find(n)+prime(n);
for(i=1001;i<=m;i++)
{
if(i%2&&i%3&&i%5&&i%7&&i%11)
count+=prime(i);
}
}
else
{
for(i=n;i<=m;i++)
{
if(i%2&&i%3&&i%5&&i%7&&i%11)
count+=prime(i);
}
}
printf("%d\n",count);
}
}
}

[此贴子已经被作者于2007-4-19 19:36:15编辑过]


2007-04-18 11:25
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
得分:0 
母牛比素数好数
n大于4之后当前数目等于前一个加三年前的数目
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct node
{
int i;
struct node *p;
}link;
void main()
{
int i,n;
link *head,*end,*before;
while(scanf("%d",&n)!=EOF)
{
if(n<4)
printf("1\n");
else
{
head=(link *)malloc(sizeof(link));
end=head;
end->i=1;
i=3;
while(i--)
{
before=(link *)malloc(sizeof(link));
end->p=before;
before->i=1;
end=before;
}
before=head->p->p;
end->p=head;
n-=3;
while(n--)
{
end->i=before->i+head->i;
before=end;
end=end->p;
head=head->p;
}
printf("%d\n",before->i);
free(head->p);
free(head);
free(before);
free(end);
}
}
}

2007-04-18 14:20
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
得分:0 
高精度去位运算

改进了一下希望不要超时间了

#include<stdio.h>
#include<string.h>
void main()
{
char a[250];
int i,j,m,n;
while(scanf("%s %d",a,&m)!=EOF)
{
n=strlen(a);
if(m==n)
{
printf("0\n");
continue;
}
i=0;
while(m--)
{
for(;a[i];i++)
{
if(a[i]==' ')
continue;
else
{
for(j=i+1;a[j]&&a[j]==' ';j++);
if(j==n)
{
a[i]=' ';
break;
}
else
{
if(a[i]>a[j])
{
a[i]=' ';
break;
}
}
}
}
for(i--;i>=0&&a[i]==' ';i--);
}
for(i=0;a[i];i++)
{
if(a[i]!=' ')
printf("%c",a[i]);
}
printf("\n");
}
}

差不多了,中文题目都给消灭了

[此贴子已经被作者于2007-4-19 20:08:43编辑过]


2007-04-18 20:31
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
得分:0 
上次应该是输出格式错误
第三题:扬辉三角
#include<stdio.h>
void main()
{
int a[35];
int i,j,k,l,flag=1;
while(scanf("%d",&k)!=EOF)
{
printf("\nCase %d\n",flag);
printf("1\n");
if(k==1)
continue;
for(i=1;i<34;i++)
a[i]=0;
a[0]=1;
l=1;
while(k--)
{
printf("1 ");
for(i=1;a[i];i++)
{
j=a[i];
a[i]=a[i]+l;
printf("%d ",a[i]);
l=j;
}
a[i]=1;
printf("1\n");
}
flag++;
}
}

[此贴子已经被作者于2007-4-19 18:27:47编辑过]


2007-04-18 21:07
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
得分:0 
26楼时间不够
27楼和24楼错误,其它均正确,继续努力

雁无留踪之意,水无取影之心
2007-04-18 21:39
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
得分:0 
就不信过不了
#include<stdio.h>
void main()
{
int a[20],n,i,j,right,left;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
right=i;
for(j=i;j<n;j++)
{
if(a[j]<a

)
right=j;
}
left=a[i];
a[i]=a[align=right];
a[align=right]=left;
}
left=right=0;
for(i=n-1;i>=0;i--)
{
if(left<=0)
left+=a[i];
else
left-=a[i];
}
left=left>0?left:0-left;
printf("%d\n",left);
}
} [align=right][此贴子已经被作者于2007-4-21 21:32:54编辑过]


2007-04-18 21:58
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
得分:0 
改了,再给提交一下
#include<stdio.h>
void main()
{
long a[20]={0};
int n,i=0,j,b[20]={0},c[20]={0},max,flag;
while(scanf("%ld",&a[i])!=EOF&&i<20){i++;}
for(n=i,i=b[0]=1;i<n;i++)
{
max=0;
for(j=i-1;j>=0;j--)
{
if(a[j]>a[i]&&b[j]>max)
max=b[j]+1;
}
b[i]=max;
}
for(i=0,max=0;i<n;i++)
{
if(b[i]>max)
max=b[i];
}
for(i=0;i<n;i++)
b[i]=0;
c[0]=a[0];
for(i=0;i<n;i++)
{
flag=1;
for(j=0;c[j]!=0;j++)
{
if(a[i]<=c[j])
{
b[j]++;
c[j]=a[i];
flag=0;
break;
}
}
if(flag)
{
c[j]=a[i];
b[j]++;
}
}
for(i=0;c[i]!=0&&i<n;i++);
printf("%d %d\n",max,i);
}

[此贴子已经被作者于2007-4-20 17:14:05编辑过]


2007-04-19 18:22



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-128407-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 1.008043 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved