ACM | ACM Test 240111
7-1 三角形判断
分数 25
给定三条线段的长度，如何判断它们能组成一个什么类型的三角形呢？
输入格式:
输入数据第一行是一个正整数 \(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代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
while(n--){
int a,b,c;
cin>>a>>b>>c;
if(a>b) swap(a,b);
if(b>c) swap(b,c);
if(a>b) swap(a,b);
if(a+b>c){
if(a*a+b*b==c*c) cout<<"Right triangle"<<endl;
else if(a*a+b*b>c*c) cout<<"Acute triangle"<<endl;
else cout<<"Obtuse triangle"<<endl;
}else{
cout<<"Impossible!"<<endl;
}
}
return 0;
}7-2 勇敢争第一
分数 20
在杭电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代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
#include<bits/stdc++.h>
using namespace std;
struct student{
string name;
int num,time;
};
bool cmp(student& a,student &b){
if(a.num == b.num)
return a.time<b.time;
return a.num>b.num;
}
int main(){
int c;
cin>>c;
while(c--){
int n,m;
cin>>n>>m;
student stu[n];
for(int i=0;i<n;i++){
cin>>stu[i].name>>stu[i].num>>stu[i].time;
}
sort(stu,stu+n,cmp);
for(int i=0;i<m;i++){
cout<<stu[i].name<<" "<<stu[i].num<<" "<<stu[i].time<<endl;
}
cout<<endl;
}
return 0;
}7-3 一起过生日
分数 20
杭州电子科技大学附属小学有个优秀的传统，每隔一段时间，会给班里的近期过生日的同学举办一场生日 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 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
#include<bits/stdc++.h>
using namespace std;
struct student{
string name;
int y,m,d;
};
int main(){
int n;
while(cin>>n){
student stu[n];
for(int i=0;i<n;i++){
cin>>stu[i].name>>stu[i].y>>stu[i].m>>stu[i].d;
}
int m1,d1,m2,d2;
cin>>m1>>d1>>m2>>d2;
bool selected;
if(m1!=m2){
for(int i=0;i<n;i++){
selected=false;
if(stu[i].m<m2 && stu[i].m>m1) selected=true;
if(stu[i].m==m2 && stu[i].d<=d2) selected=true;
if(stu[i].m==m1 && stu[i].d>=d1) selected=true;
if(selected){
cout<<stu[i].name<<" ";
}
}
}else{
if(d1>d2) swap(d1,d2);
for(int i=0;i<n;i++){
if(stu[i].m==m1 && stu[i].d>=d1 && stu[i].d<=d2){
cout<<stu[i].name<<" ";
}
}
}
cout<<endl;
}
return 0;
}7-4 杰克马抓牛
分数 15
Jack Ma 退休后过上了田园生活，他养了一群牛。
有一天有人告诉他一头牛逃跑了，牛现在的位置在 \(K\) 点，他现在处于 \(N\) 点。
假设他们都只能沿着他们所在的直线行走，Jack Ma 有两种行动方式：
走路：在一分钟之内，从 \(X\) 点向前移动一个位置到 \(X + 1\)，或者向后移动到 \(X - 1\)。
瞬移：在一分钟之内，从 \(X\) 点移动到 \(2 * X\) 点处。
假设牛是不知道已经被发现逃跑了，一直在原地未动，请问 Jack Ma 最少需要多少时间能追到牛。
输入格式:
输入包含多个测试数据。
每个测试数据包含两个整数 \(N, K(0 <= N, K <= 100,000)\) ，分别表示 Jack Ma 和牛在直线上的位置。
输出格式:
对于每组测试数据，请输出追到牛最少需要花费多少分钟。
每组数据输出一行。
输入样例:
5 17输出样例:
4代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
#include<bits/stdc++.h>
using namespace std;
const int maxa=200000;
int main(){
int n,k;
while(cin>>n>>k){
queue<int> q;
bool used[maxa];
int depth[maxa];
memset(used,false,sizeof(used));
q.push(n);
used[n]=true;
depth[n]=0;
while(!q.empty()){
int now=q.front();
q.pop();
if(now==k){
cout<<depth[now]<<endl;
break;
}
if(now-1>=0 && !used[now-1]){
q.push(now-1);
used[now-1]=true;
depth[now-1]=depth[now]+1;
}
if(now+1<maxa-1 && !used[now+1]){
q.push(now+1);
used[now+1]=true;
depth[now+1]=depth[now]+1;
}
if(now*2<maxa && !used[now*2]){
q.push(now*2);
used[now*2]=true;
depth[now*2]=depth[now]+1;
}
}
}
return 0;
}7-5 小猫和老鼠
分数 10
小老鼠准备了 \(M\) 磅的猫粮，准备去和看守仓库的小猫做交易，因为仓库里有小老鼠喜欢吃的五香豆。
仓库有N个房间；
第 \(i\) 个房间有 \(J[i]\) 磅的五香豆，需要用 \(F[i]\) 磅的猫粮去交换；
需要指出的是：
老鼠如果要和某个房间的小猫做交易，就必须交换该房间所有的五香豆！
还有个特殊的情况，小老鼠有强迫症——它一定要把自己所有的猫粮都用完才行！
现在，请帮忙计算一下，在必须用完所有的猫粮的前提下，小老鼠通过交易最多能够得到多少磅的五香豆？
输入格式:
输入包含多组测试用例。
每组测试数据首先一行是 \(2\)
个非负整数 \(M\) 和 \(N\)，接着的 \(N\) 行，每行分别包含 \(2\)
个非负整数J[i]和F[i]，数据的具体含义详见题目描述。
输入数据以两个-1结束。
题目保证所有的数据都不超过\(1000\).
输出格式:
请计算并输出小老鼠最多能够得到的五香豆数量，如果不能满足小老鼠的强迫症，请输出-1；
每组数据输出一行。
输入样例:
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1输出样例:
11
-1代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
7-6 抗旱和救灾
分数 10
正所谓——“百年不遇年年遇”！
某年夏天，中国西南诸省再次出现了“百年不遇”的严重旱情！
由于灾情越来越严重，很多学校师生的用水困难已成为最急需解决的问题，而要给各学校提供用水，就必须先知道各学校是否与水库有道路相连。
刘二丁——国家防汛抗旱总指挥部总指挥，现在想请你编写一个程序，读入所有道路的信息，计算有多少学校没有路与水库相通。
同学们，好好学算法，为刘总指挥分忧~
输入格式:
输入有多组数据。
每组数据第一行包括两个正整数 \(n\) ，\(m（0<n<1000, 0<m<=(n*(n+1)/2)\)，\(n\) 表示学校的数目，\(m\)表示道路的数目），学校用\(1\)到\(n\)的整数编号，水库的编号永远记为\(0\)；
接下来有m行，每行有两个数a和b，a和b用一个空格分开，表示a到b有一条路。
请处理到文件结束。
输出格式:
对于每组输入数据：
如果所有的学校均与水库相通，则请在一行内输出0；
如果有学校不通水库，则请输出与水库无路连接的学校个数；
每组数据的输出占一行。
输入样例:
4 4
0 1
0 2
1 2
2 3输出样例:
1代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
#include<bits/stdc++.h>
using namespace std;
const int maxa=200000;
void merge(int* array,int to,int from,int size){
if(array[to]!=array[from]){
int temp=array[from];
for(int i=0;i<size;i++){
if(array[i]==temp){
array[i]=array[to];
}
}
}
}
int main(){
int n,m;
while(cin>>n>>m){
int school[n+1];
for(int i=0;i<n+1;i++){
school[i]=i;
}
int a,b;
for(int i=0;i<m;i++){
cin>>a>>b;
merge(school,a,b,n+1);
// if(a==0){
// merge(school,a,b,n);
// }else if(b==0){
// merge(school,b,a,n);
// }else{
// merge(school,a,b,n);
// }
// for(int i=0;i<n+1;i++){
// cout<<school[i]<<" ";
// }
// cout<<endl;
}
int count=0;
for(int i=1;i<n+1;i++){
if(school[i]!=school[0]){
count++;
}
}
cout<<count<<endl;
}
return 0;
}