codeforces #120 div 2 (Virtual Participation)

两题QAQ

A：7分钟1A 有n个大人m个小孩乘公交车，票价每人一元，一个大人最多免费带一个小孩，没有大人陪同的小孩不能乘车。问是否有解，如果有解输出所有乘客付的钱的可能的最小值和可能的最大值。

思路：最小值就是先尽量利用每个大人带一个孩子。最大值就是把所有孩子都给一个大人。

特殊情况是：没有大人的时候，孩子不能乘车，无解。没有小孩的时候，大人没办法免费带孩子，也要特殊考虑。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年03月24日 星期四 12时24分27秒
 4File Name :code/cf/#120/A.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int n,m;
34int mx,mi;
35int main()
36{
37	#ifndef  ONLINE_JUDGE
38	freopen("code/in.txt","r",stdin);
39  #endif
40
41	cin>>n>>m;
42	if (n==0&&m>0)
43	{
44	    puts("Impossible");
45	    return 0;
46	}
47	if (n==0&&m==0)
48	{
49	    cout<<0<<" "<<0<<endl;
50	    return 0;
51	}
52	if (m==0&&n>0)
53	{
54	    cout<<n<<" "<<n<<endl;
55	    return 0 ;
56	}
57	if (n>=m)
58	{
59	    mi = n ;
60	    mx = n-1+m;
61	}
62	else
63	{
64	    mi = n + m-n;
65	    mx = n-1+m;
66	}
67	cout<<mi<<" "<<mx<<endl;
68
69
70  #ifndef ONLINE_JUDGE
71  fclose(stdin);
72  #endif
73    return 0;
74}

B:有两个被包围的城市，给出城市的坐标以及敌人距离城市的距离。敌人向着城市移动。要求建一个雷达，使得雷达能够感应到两伙敌人（分别朝着两个方向移动）的“the start of the movements”。问雷达的最小半径是多少。

反思：思维不够清楚，太呆

思路：两个圆有**五种（一开始想成了三种，所以wa7）**位置关系，分别考虑。

相离时，答案为（圆心距-半径之和）/2

外切时：把雷达建在切点，答案为0.

相交时：把雷达建在交点，答案为0

内切时：把雷达建在交点，答案为0.

内含时：答案为（abs(半径之差)-圆心距离）/2.

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年03月24日 星期四 12时53分05秒
 4File Name :code/cf/#120/BB.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int a,b,r1;
34int c,d,r2;
35int dblcmp(double d)
36{
37    return d<-eps?-1:d>eps;
38}
39int main()
40{
41	#ifndef  ONLINE_JUDGE
42	freopen("code/in.txt","r",stdin);
43  #endif
44	cin>>a>>b>>r1;
45	cin>>c>>d>>r2;
46	double dis = sqrt((a-c)*(a-c)+(b-d)*(b-d));
47	double r = r1+r2;
48	if (dblcmp(r-dis)==0)
49	{
50	    puts("0.0000000000000000");
51	    return 0;
52	}
53
54	if (dblcmp(r-dis)<0)
55	{
56	    double ans = (dis-r)*0.5;
57	    printf("%.16f\n",ans);
58	}
59	if (dblcmp(r-dis)>0)
60	{
61	    if (dblcmp(dis-abs(r1-r2))>=0)
62	    {
63		puts("0.00000000000000");
64	    }
65	    if (dblcmp(dis-abs(r1-r2))<0)
66	    {
67		double ans = (abs(r1-r2)-dis)*0.5;
68		printf("%.15f\n",ans);
69	    }
70
71	}
72  #ifndef ONLINE_JUDGE
73  fclose(stdin);
74  #endif
75    return 0;
76}

C:给出一个pair 和int 序列，问能否恢复成一个合法的类型表示。如果能，保证有唯一解，输出这个唯一解。

细节略多。

没搞出来QAQ

相关文章