2009 ACM-ICPC世界总决赛试题分析1-3

1

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
using namespace std;
struct node
{
	int x,y;
};
node a[10];
int s[10],c[10];
int n;

bool check1(double mid)
{
	double k=a[c[1]].x;
	for(int i=2;i<=n;i++)
	{
		k=k+mid;
		if(k>a[c[i]].y)
			return false;
		if(k<a[c[i]].x)
			k=a[c[i]].x;
	}
	return true;
}

bool check(double mid)
{
	for(int i=1;i<=n;i++)
		c[i]=i;
	for(int i=1;i<=s[n];i++)
	{
		if(check1(mid))
			return true;
		next_permutation(c+1,c+n+1);
	}
	return false;
}

int main()
{
	int cnt=0;
	s[1]=1;
	for(int i=2;i<=10;i++)
		s[i]=s[i-1]*i;
	while(scanf("%d",&n),n!=0)
	{
		for(int i=1;i<=n;i++)
			scanf("%d%d",&a[i].x,&a[i].y);
		double l=0,r=1500;
		while(l+1e-5<r)
		{
			double mid=(l+r)/2;
			if(check(mid))
				l=mid;
			else
				r=mid;
		}
		int s=(int)l,t=(int)((l-s)*60+0.5);
		if(t==60)
		{
			t=0;
			s++;
		}
		printf("Case %d: %d:",++cnt,s);
		if(t<10)
			printf("0%dn",t);
		else
			printf("%dn",t);
	}
	return 0;
}

#include<iostream>
#include<string>
#include<string.h>
#include<stdlib.h>
using namespace std;
struct dat_edge
{
	int aim,last;
}edge[201];

int n,m,k,inde[101],coun[101],tmp_coun[101],pl[101],len_edge,num_key,key[300][101];
char kind[101];

void insert_edge(int x,int y)
{
	len_edge++;
	edge[len_edge].aim=y;
	edge[len_edge].last=pl[x];
	pl[x]=len_edge;
}

void init(int o,string z)
{
	int p,i,num;
	string t;
	p=1;
	z+=' ';
	for(i=1;i<z.length();i++)
		if(z[i]==' ')
		{
			t=z.substr(p,i-p);
			if(t[0]=='i')
				num=0;
			else
				num=n;
			if(t.length()==2)
				num+=t[1]-'0';
			else
			{
				num+=(t[1]-'0')*10+t[2]-'0';
			}
			coun[o]++;
			insert_edge(num,o);
			p=i+1;
		}
}

bool solve(int key[],int poi,int sta)
{
	int i,p,o,w,tmp,que[101],f[101];
	for(i=1;i<=n+m+k;i++)
	{
		f[i]=0;
	}
	for(i=1;i<=n;i++)
		f[i]=key[i];
	for(i=1;i<=m;i++)
	{
		if(kind[i]=='a')
			f[i+n]=1;
		else
			f[i+n]=0;
	}
	o=n;w=0;
	for(i=1;i<=n;i++)
		que[i]=i;
	while(w<o)
	{
		w++;
		if(que[w]==poi)
		{
			if(sta==2)
				f[que[w]]=!f[que[w]];
			else
				f[que[w]]=sta;
		}
		p=pl[que[w]];
		while(p!=-1)
		{
			coun[edge[p].aim]--;
			if(coun[edge[p].aim]==0)
			{
				que[++o]=edge[p].aim;
			}
			tmp=edge[p].aim;
			if(kind[tmp-n]=='a')
			{
				if(f[que[w]]==0)
					f[tmp]=0;
			}
			else if(kind[tmp-n]=='o')
			{
				if(f[que[w]]==1)
					f[tmp]=1;
			}
			else if(kind[tmp-n]=='x')
			{
				f[tmp]=f[tmp]^f[que[w]];
			}
			else
			{
				f[tmp]=!f[que[w]];
			}
			p=edge[p].last;
		}
	}
	for(i=1;i<=n+m+k;i++)
		coun[i]=tmp_coun[i];
	for(i=1;i<=k;i++)
	{
		if(f[inde[i]+n]!=key[n+i])
			return false;
	}
	return true;
}

void work(int t)
{
	int i,j,p,ans1,ans2,coun_ans;
	bool ok=true;
	for(i=1;i<=num_key;i++)
	{
		if(!solve(key[i],-1,-1))
		{
			ok=false;
			break;
		}
	}
	if(ok)
	{
		cout<<"Case "<<t<<": No faults detectedn";
		return;
	}
	ans1=ans2=coun_ans=0;
	for(i=1;i<=m;i++)
	{
		for(j=0;j<=2;j++)
		{
			ok=true;
			for(p=1;p<=num_key;p++)
			{
				ok=solve(key[p],i+n,j);
				if(!ok)
					break;
			}
			if(ok)
			{
				ans1=i;
				ans2=j;
				coun_ans++;
			}
		}
	}
	if(coun_ans!=1)
	{
		cout<<"Case "<<t<<": Unable to totally classify the failuren";
		return;
	}
	if(ans2==2)
	{
		cout<<"Case "<<t<<": Gate "<<ans1<<" is failing; output invertedn";
		return;
	}
	if(ans2==0)
	{
		cout<<"Case "<<t<<": Gate "<<ans1<<" is failing; output stuck at 0n";
		return;
	}
	if(ans2==1)
	{
		cout<<"Case "<<t<<": Gate "<<ans1<<" is failing; output stuck at 1n";
		return;
	}
}

int main()
{
	int t,i,j;
	string z;
	t=0;
	while(cin>>n>>m>>k && n+m+k!=0)
	{
		t++;
		memset(coun,0,sizeof(coun));
		len_edge=-1;
		for(i=1;i<=n+m+k;i++)
			pl[i]=-1;
		for(i=1;i<=m;i++)
		{
			cin>>kind[i];
			getline(cin,z);
			init(i+n,z);
		}
		for(i=1;i<=n+m+k;i++)
			tmp_coun[i]=coun[i];
		for(i=1;i<=k;i++)
			cin>>inde[i];
		cin>>num_key;
		for(i=1;i<=num_key;i++)
			for(j=1;j<=n+k;j++)
				cin>>key[i][j];
		work(t);
	}
	return 0;
}

#include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>using namespace std;#define FOR(I,A,B) for(I=int(A);I<int(B);++I)#define MEM(A,B) memset(A,B,sizeof(A));#define CPY(A,B) memcpy(A,B,sizeof(B));const double pi=acos(-1.0);struct TPoint{	double x,y,z;	void get(double a,double b,double c)	{		x=a;y=b;z=c;	}};TPoint p[5];TPoint A,B;int a1,a2,a3,a4,ca;double l;void init(){	l=5*sqrt(2.);	p[0].get(0,0,l);	p[1].get(l,0,0);	p[2].get(0,l,0);	p[3].get(-l,0,0);	p[4].get(0,-l,0);}double eps(double x){	return x<1e-6&&x>-1e-6;}void getpoint(double a1,double a2,TPoint &A){	double l2,r,aa=(int)a1%90;	a1=a1/180*pi;	a2=a2/180*pi;	aa=aa/180*pi;	l2=l/(sin(aa)+cos(aa));	r=l2*l/(l*sin(a2) + l2*cos(a2));	A.x=r*sin(a2)*cos(a1);	A.y=r*sin(a2)*sin(a1);	A.z=r*cos(a2);}double sqr(double x){	return x*x;}double dis(TPoint a,TPoint b){	return sqrt(sqr(a.x-b.x) + sqr(a.y-b.y) + sqr(a.z-b.z));}int pre(int x){	return (x+3)%4;}int nxt(int x){	return (x+1)%4;}TPoint point(double ra,int x,int y){	TPoint ret;	ret.x=(p[x].x-p[y].x)*ra + p[y].x;	ret.y=(p[x].y-p[y].y)*ra + p[y].y;	ret.z=(p[x].z-p[y].z)*ra + p[y].z;	return ret;}double getang(double a,double b,double c){	if(eps(c)||eps(a-b-c))		return 0;	return acos((sqr(a)+sqr(b)-sqr(c))/(2*a*b));}double cal(int p1,int p2,TPoint A,TPoint B){	TPoint C,D;	double L,R,mid1,mid2,ret(1e10);	if(a4>90)	{		int i;		a4=180-a4;		FOR(i,0,4)		{			L=0;R=1;			while(R-L>1e-4)			{				mid1=L+(R-L)/3;				C=point(mid1,i+1,nxt(i)+1);				mid2=R-(R-L)/3;				D=point(mid2,i+1,nxt(i)+1);				if(cal(p1,i,A,C)+cal(i,p2,C,B)>cal(p1,i,A,D)+cal(i,p2,D,B))					L=mid1;				else					R=mid2;			}			ret=min(ret,cal(p1,i,A,C)+cal(i,p2,C,B));		}		return ret;	}	if(p1==p2)		return dis(A,B);	if(nxt(p2)==p1)	{		swap(p1,p2);		swap(A,B);	}	if(nxt(p1)==p2)	{		double an,a=dis(A,p[0]),b=dis(B,p[0]);		an=getang(10,a,dis(A,p[nxt(p1)+1]))+getang(10,b,dis(B,p[nxt(p1)+1]));		return sqrt(sqr(a)+sqr(b)-2*a*b*cos(an));	}	int i;	L=0;R=1;	while(R-L>1e-4)	{		mid1=L+(R-L)/3;		C=point(mid1,0,p1+1);		mid2=R-(R-L)/3;		D=point(mid2,0,p1+1);		if(dis(A,C)+cal(pre(p1),p2,C,B)>cal(pre(p1),p2,D,B)+dis(A,D))			L=mid1;		else			R=mid2;	}	ret=cal(pre(p1),p2,C,B)+dis(A,C);	L=0;R=1;	while(R-L>1e-4)	{		mid1=L+(R-L)/3;		C=point(mid1,0,nxt(p1)+1);		mid2=R-(R-L)/3;		D=point(mid2,0,nxt(p1)+1);		if(cal(nxt(p1),p2,C,B)+dis(A,C)>cal(nxt(p1),p2,D,B)+dis(A,D))			L=mid1;		else			R=mid2;	}	ret=min(ret,cal(nxt(p1),p2,C,B)+dis(A,C));	return ret;}int main(){	init();	while(scanf("%d%d%d%d",&a1,&a2,&a3,&a4),a1+a2+a3+a4!=-4)	{		if(a2>90&&a4>90)			a2=180-a2,a4=180-a4;		if(a2>a4)		{			swap(a1,a3);			swap(a2,a4);		}		getpoint(a1,a2,A);		if(a4>90)			getpoint(a3,180-a4,B);		else			getpoint(a3,a4,B);		printf("Case %d: %.3lfn",++ca,cal(a1/90,a3/90,A,B));			}	return 0;}

最后

以上就是坚强芒果为你收集整理的2009 ACM-ICPC世界总决赛试题分析1-3的全部内容，希望文章能够帮你解决2009 ACM-ICPC世界总决赛试题分析1-3所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。