ACM | ACM Test 231029
7-1 三角形判断
给定三条线段的长度,如何判断它们能组成一个什么类型的三角形呢?
输入格式:
输入数据第一行是一个正整数 \(N\),表示有 \(N\) 组测试用例。
接下来 \(N\) 行,每行包含三个正整数 \(A, B, C (0 < A, B, C < 10000)\),表示三条线段的长度。
输出格式:
对于每组数据给定的三条线段:
如果能够组成直角三角形,请输出 "Right triangle" ;
如果能够组成锐角三角形,请输出 "Acute triangle" ;
如果能够组成钝角三角形,请输出 "Obtuse triangle" ;
如果不能组成三角形,请输出"Impossible!";
所有的输出,都不包含双引号,参见样例输出。
输入样例:
3
12 12 12
4 6 12
6 8 12
输出样例:
Acute triangle
Impossible!
Obtuse triangle
#include<stdio.h>
int main(){
int N;
scanf("%d",&N);
while(N--){
int a,b,c,t;
scanf("%d%d%d",&a,&b,&c);
if(a>b){
t=a;a=b;b=t;
}
if(b>c){
t=b;b=c;c=t;
}
if(a>b){
t=a;a=b;b=t;
}
if(a+b>c && b+c>a && a+c>b){
if(a*a+b*b>c*c){
printf("Acute triangle\n");
}else if(a*a+b*b<c*c){
printf("Obtuse triangle\n");
}else{
printf("Right triangle\n");
}
}else{
printf("Impossible!\n");
}
}
return 0;
}
7-2 奋勇争先续
在杭电ACM课的每次测试中,每一次大家都奋勇争先,想拿下第一名。
现在已知某次测验的每位同学的解题数量和罚时,希望你能够告诉老师前几名是哪些同学。
排名规则是这样的,首先依据解题数量从大到小排名,若解题数量相同,则比较罚时,罚时少的排名靠前。
输入格式:
第一行是数据组数 \(C(1 <= C <= 10)\),代表有 \(C\) 组测试数据。
每一组数据第一行为两个 \(N(2 < N <= 1000)\) 和 \(M(1 <= M <= N)\),\(N\) 表示有 \(N\) 个人的成绩,\(M\) 表示老师需要你输出前 \(M\) 名的名单。
接下来 \(N\) 行,每一行依次给出名字 Name,解题数量 Num 和罚时 Time(名字的长度最大为 \(10, 1 <= Num <= 10, 10 <= Time <= 100000\))。
输出格式:
每组测试数据输出 M 行,每行依次为是名字、解题数量和罚时,中间用空格隔开。
每组测试数据后空一行。
输入样例:
1
3 3
Bob 5 50
Alice 4 46
John 5 48
输出样例:
John 5 48
Bob 5 50
Alice 4 46
#include<stdio.h>
#include<string.h>
char name[1001][11];
int num[1001];
int time[1001];
void swap(int j){
char temp[11];
strcpy(temp,name[j]);
strcpy(name[j],name[j+1]);
strcpy(name[j+1],temp);
int tmp=num[j];
num[j]=num[j+1];
num[j+1]=tmp;
tmp=time[j];
time[j]=time[j+1];
time[j+1]=tmp;
}
int main(){
int C;
scanf("%d",&C);
while(C--){
int N,M;
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++){
scanf("%s%d%d",name[i],num+i,time+i);
}
for(int i=0;i<N;i++){
for(int j=0;j<N-i-1;j++){
if(num[j]<num[j+1]){
swap(j);
}else if(num[j]==num[j+1] && time[j]>time[j+1]){
swap(j);
}
}
}
for(int i=0;i<M;i++){
printf("%s %d %d\n",name[i],num[i],time[i]);
}
printf("\n");
}
return 0;
}
7-3 素数输出续
给定一个正整数 \(N\),请输出小于等于 \(N\) 的素数个数。
输入格式:
输入包含多组测试数据,每组数据占一行,包括一个正整数 \(N(2<=N<=100000)\)。
输出格式:
对于每组数据给定的 \(N\),请输出一个正整数,表示小于等于 \(N\) 的素数个数,每组输出占一行。
输入样例:
10
20
输出样例:
4
8
#include<stdio.h>
int primes[10000]={2,3,5,7,11,13,17,19};
int count=8;
int isprime(int a){
for(int i=0;i<count;i++){
if(a%primes[i]==0){
return 0;
}
}
return 1;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
count=8;
for(int i=23;i<=n;i+=2){
if(isprime(i)){
primes[count++]=i;
}
}
if(n>=20){
printf("%d\n",count);
}else{
//printf("1\n");
int ans=0;
for(int i=0;i<8;i++){
if(primes[i]<=n){
ans++;
}
}
printf("%d\n",ans);
}
}
return 0;
}
// #include<stdio.h>
// int primes[10000]={2};
// int count=1;
// int isprime(int n){
// for(int i=0;i<count;i+=2){
// if(n%primes[i]==0){
// return 0;
// }
// }
// return 1;
// }
// int main(){
// int n;
// while(scanf("%d",&n)!=EOF){
// int cnt=1;
// for(int i=3;i<=n;i+=2){
// if(isprime(i)){
// cnt++;
// }
// }
// printf("%d\n",cnt);
// }
// return 0;
// }
7-4 多级排序,逸天专备
说到排序,我们都知道这是编程人员必备的知识,更不用说信奥了。
朱逸天,丁爸编程培训班的首期学员,尽管0基础开始,但是进步很大,已经熟练掌握了各种排序的实现。
现在,朱逸天专门准备了这么一个题目,想测试一下同班同学的你,看看你是否也熟练掌握了排序。
假设丁爸信奥培训班共有\(N(N<100)\)名同学,已知各位同学的详细信息(姓名,年龄,分数),现在请对培训班的全体同学做一个排序。
排序的规则要求如下:
1、首先按照分数从高到低进行排序;
2、如果分数相同,则年龄小的排名靠前;
3、如果依然不能区分,再按照姓名的字典序排列;
考验你的时候到了,你是否能像朱逸天一样熟练掌握排序呢?
输入格式:
输入包含多组测试用例;
每组数据首先是一个正整数\(N\),表示培训班有\(N\)位同学,每位同学的信息占一行,依次是姓名Name、年龄Age和分数Score。
其中,姓名Name是长度不超过10的无空格字符串,年龄Age是不大于20的正整数,分数Score是不超过100的浮点数。
输出格式:
请输出排序后的全班同学信息,其中,分数保留2位小数。
格式参见样例。
输入样例:
6
jaa 18 99.5
bbb 19 100
kcc 19 99
tdd 20 100
abc 18 100
see 19 100
输出样例:
abc 18 100.00
bbb 19 100.00
see 19 100.00
tdd 20 100.00
jaa 18 99.50
kcc 19 99.00
#include<stdio.h>
#include<math.h>
#include<string.h>
struct stu{
char name[11];
int age;
double score;
}stu[100];
void swap(int j){
char temp[11];
strcpy(temp,&stu[j].name);
strcpy(&stu[j].name,&stu[j+1].name);
strcpy(&stu[j+1].name,temp);
int tmp=stu[j].age;
stu[j].age=stu[j+1].age;
stu[j+1].age=tmp;
double tmp1;
tmp1=stu[j].score;
stu[j].score=stu[j+1].score;
stu[j+1].score=tmp1;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
scanf("%s %d %lf",&stu[i].name,&stu[i].age,&stu[i].score);
}
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(fabs(stu[j].score-stu[j+1].score)<1e-6){
if(stu[j].age==stu[j+1].age){
if(strcmp(&stu[j].name,&stu[j+1].name)>0){
swap(j);
}
}else if(stu[j].age>stu[j+1].age){
swap(j);
}
}else if(stu[j].score<stu[j+1].score){
swap(j);
}
}
}
for(int i=0;i<n;i++){
printf("%s %d %.2lf\n",stu[i].name,stu[i].age,stu[i].score);
}
}
return 0;
}
7-5 逛超市
周末又到了,你准备去采购一些零食。今天你一共带 \(V\) 元钱,来到了热闹非凡的“一元超市”,就是这里的所有东西都只卖一元。
超市里有 \(N\) 种不同的零食,虽然每种零食都只要一元,但是对于你来说能够得到的满足度不一样,并且每种零食你吃一次后都不再想吃了。
现在告诉你每种零食能够获得的满足度,你能计算出能够获得的最大满足度是多少吗?
输入格式:
输入包含多组测试数据,每组测试数据第一行是两个正整数 \(N\) 和 \(V(0 < N <= 1000, 0 <= V <= N)\),分别表示零食的种数和带的钱。接下来一行包含 \(N\) 个正整数,分别表示每种零食可以获得的满足度。
输出格式:
每组测试数据输出一个正整数,表示可以获得的最大满足度。
每组输出占一行。
输入样例:
3 2
2 1 3
输出样例:
5
#include<stdio.h>
int compare(const int *a,const int *b){
return -*(int*)a+*(int*)b;
}
int main(){
int N,V;
int freshments[1000];
int ans;
while(scanf("%d%d",&N,&V)!=EOF){
ans=0;
for(int i=0;i<N;i++){
scanf("%d",&freshments[i]);
}
qsort(freshments,N,sizeof(int),compare);
for(int i=0;i<V;i++){
ans+=freshments[i];
}
printf("%d\n",ans);
}
return 0;
}
7-6 一起过生日
杭州电子科技大学附属小学有个优秀的传统,每隔一段时间,会给班里的近期过生日的同学举办一场生日 Party!老师会给出一个生日起止日期来确定生日 Party 的小寿星。
输入格式:
输入包含多组测试数据。
每组数据第一行,包括一个正整数 \(N(0 <= N <= 40)\),表示某个班的学生人数,接下来有 \(N\) 行数据,每行包含一个同学的姓名,以及出生年、月、日。
每组数据的最后一行,包括 4 个正整数 \(m1、d1、m2、d2\),分别表示生日 Party 的小寿星生日起止月和日(包含),其中 \(m1 <= m2\)。
输出格式:
每组数据输出一行小寿星的名单(按照原名单的次序),每个名字后面跟一个空格。
输入样例:
5
Tom 2009 10 15
Kate 2010 7 20
David 2010 6 30
Kevin 2009 7 3
Sarah 2010 3 8
7 1 7 30
输出样例: Kate Kevin
#include<stdio.h>
int main(){
int N;
char name[40][10];
int year[40];
int month[40];
int day[40];
int m1,d1,m2,d2;
while(scanf("%d",&N)!=EOF){
for(int i=0;i<N;i++){
scanf("%s %d %d %d",name[i],year+i,month+i,day+i);
}
scanf("%d%d%d%d",&m1,&d1,&m2,&d2);
for(int i=0;i<N;i++){
if(m1==m2){
if(month[i]==m1 && day[i]<=d2 && day[i]>=d1){
printf("%s ",name[i]);
}
continue;
}else if((month[i]==m1 && day[i]>=d1) || (month[i]==m2 && day[i]<=d2) || (month[i]>m1 && month[i]<m2)){
printf("%s ",name[i]);
}
}
printf("\n");
}
return 0;
}
7-7 人在江湖,浩然养猪
祝浩然同学在学习信奥的过程中一直是顺风顺水。
不知为何,突然有一天,他厌倦了这一切,毅然决然要回老家养猪!
我想,这也许是因为祝浩然同学是个有情怀的爱国青年,他想实业救国。
也许某一天,祝浩然同学能在养猪界一统江湖~
说干就干!
在2018年1月1日,祝浩然同学买了一只刚出生的母猪幼仔,假设每只小母猪从第3个年头开始,每年的第一天都会生出4只小母猪,同时,祝浩然同学还会在每年的12月31日售出所有差一天就要年满5周岁的猪。
请预测:
在第N年(2018年是第1年,2019是第2年,依次类推)的今天(6月16日),祝浩然的养猪场会存栏多少只猪?
输入格式:
输入数据第一行是一个整数\(T(0< T <=40)\),表示测试数据的组数。
接下来有\(T\)行,每行有一个数\(N(0< N <=40)\)表示一组测试数据,其含义如题目描述。
输出格式:
对于每个测试实例,请输出在第N年的今天母猪的数量,每组数据的输出占一行。
输入样例:
3
2
3
5
输出样例:
1
5
29
#include<stdio.h>
int main(){
int T;
scanf("%d",&T);
while(T--){
int N;
scanf("%d",&N);
int y1=1;
int y2=0;
int y3=0;
int y4=0;
int y5=0;
N--;
while(N--){
y5=y4;
y4=y3;
y3=y2;
y2=y1;
y1=4*(y3+y4+y5);
}
printf("%d\n",y1+y2+y3+y4+y5);
}
}
// 1 0 0 0 0
// 0 1 0 0 0
// 4 0 1 0 0
// 4 4 0 1 0
// 16 4 4 0 1
7-8 机器分配
某总公司拥有设备\(M\)台,准备分给下属的N个子公司。各子公司若获得这些设备,可以为总公司赚取一定的盈利。
如何分配这M台设备才能使总公司得到的盈利最大?
请输出最大盈利值。
输入格式:
输入包含多组测试数据。
每组数据第一行为两个整数\(N\),\(M\),表示有\(N\)个子公司,M台设备。
接下来是一个\(N×M\)的矩阵,其中矩阵的第\(i\)行的第\(j\)列的数\(A_{ij}\)表明第\(i\)个子公司分配\(j\)台机器的盈利。
其中:
\(N <= 100\)
\(M <= 100\)
输出格式:
请计算总公司合理分配这M台设备所获得的最大盈利。
每组数据输出一行。
输入样例:
2 3
1 2 3
2 3 4
输出样例:
4
#include<stdio.h>
#include<string.h>
int max(int a,int b){
return a>b?a:b;
}
int main(){
int N,M;
while(scanf("%d%d",&N,&M)!=EOF){
int profit[101][101];
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
scanf("%d",profit[i]+j);
}
}
int dp[101][101];
memset(dp,0,sizeof(dp));
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
dp[i][j]=max(dp[i][j],dp[i-1][j]);
for(int k=1;k<=j;k++){
dp[i][j]=max(dp[i][j],dp[i-1][j-k]+profit[i][k]);
}
}
}
// for(int i=1;i<=N;i++){
// for(int j=1;j<=M;j++){
// for(int k=1;k<=j;k++){
// if(j-k>0){
// dp[i][j]=max(dp[i][j],dp[i-1][j-k]+profit[i][k]);
// }
// }
// }
// }
printf("%d\n",dp[N][M]);
}
return 0;
}