読者です 読者をやめる 読者になる 読者になる

AOJ 1102,0155,0198

構文解析と面倒で残っていたものを片付けました。

1102
罠が多すぎる。数字が大きくてオーバーフローするとか、iではなく1iと出力しないといけないとか。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
bool ok;
char str[1024];
pair<pair<int,int>,int>eq(int a);
pair<pair<int,int>,int>ter(int a){
	if(str[a]=='('){
		pair<pair<int,int>,int>res=eq(a+1);
		res.second++;
		return res;
	}else if(str[a]=='i'){
		return make_pair(make_pair(0,1),a);
	}else{
		int res=0;
		int at=a;
		while(str[at]>='0'&&str[at]<='9'){
			res*=10;
			res+=str[at]-'0';
			if(res>10000)ok=false;
			at++;
		}
		return make_pair(make_pair(res,0),at-1);
	}
}
pair<pair<int,int>,int>fac(int a){
	pair<pair<int,int>,int>t=ter(a);
	pair<int,int>ret=t.first;
	while(str[t.second+1]=='*'){
		t=ter(t.second+2);
		int L=ret.first*t.first.first-ret.second*t.first.second;
		ret.second=ret.first*t.first.second+ret.second*t.first.first;
		ret.first=L;
		if(ret.first<-10000||ret.first>10000||ret.second<-10000||ret.second>10000)ok=false;
	}
	return make_pair(ret,t.second);
}
pair<pair<int,int>,int>eq(int a){
	pair<pair<int,int>,int>t=fac(a);
	pair<int,int>ret=t.first;
	while(str[t.second+1]=='+'||str[t.second+1]=='-'){
		if(str[t.second+1]=='+'){
			t=fac(t.second+2);
			ret.first+=t.first.first;
			ret.second+=t.first.second;
			if(ret.first<-10000||ret.first>10000||ret.second<-10000||ret.second>10000)ok=false;
		}else{
			t=fac(t.second+2);
			ret.first-=t.first.first;
			ret.second-=t.first.second;
			if(ret.first<-10000||ret.first>10000||ret.second<-10000||ret.second>10000)ok=false;
		}
	}
	return make_pair(ret,t.second);
}
int main(){
	while(~scanf("%s",str)){
		ok=true;
		pair<int,int>res=eq(0).first;
		if(!ok)printf("overflow\n");
        else{
            if(res.first){
                printf("%d",res.first);
                if(res.second>0)printf("+%di",res.second);
                else if(res.second<0)printf("%di",res.second);
                printf("\n");
            }else if(res.second)printf("%di\n",res.second);
            else printf("0\n");
        }
	}
}

0155
ダイクストラするだけなのに経路復元とか変な制約とかがあって放置していました

#include<stdio.h>
#include<stack>
#include<math.h>
using namespace std;
int dd[1000][1000];
int num[1000];
int inv[1001];
int x[1000];
int y[1000];
int vv[1000];
double nowt[1000];
int rev[1000];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++){
			scanf("%d%d%d",num+i,x+i,y+i);
			inv[num[i]]=i;
		}
		for(int i=0;i<a;i++)
			for(int j=0;j<a;j++)
				dd[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
		int b;
		scanf("%d",&b);
		for(int i=0;i<b;i++){
			int c,d;
			scanf("%d%d",&c,&d);
			c=inv[c];d=inv[d];
			for(int j=0;j<a;j++){
				vv[j]=0;
				nowt[j]=999999999;
				rev[j]=-1;
			}
			nowt[c]=0;
			for(int j=0;j<a;j++){
				double M=99999999;
				int at=0;
				for(int k=0;k<a;k++){
					if(!vv[k]&&M>nowt[k]){
						M=nowt[k];
						at=k;
					}
				}
				if(M>90000000)break;
				//printf("%d\n",at);
				vv[at]=1;
				for(int k=0;k<a;k++){
					if(!vv[k]&&dd[at][k]<=2500&&nowt[k]>nowt[at]+sqrt(dd[at][k])){
						nowt[k]=nowt[at]+sqrt(dd[at][k]);
						rev[k]=at;
					}
				}
			}
			if(!vv[d])printf("NA\n");
			else {
				stack<int>S;
				int V=d;
				while(V!=c){
					S.push(V);
					V=rev[V];
				}
				printf("%d",num[c]);
				while(S.size()){
					printf(" %d",num[S.top()]);
					S.pop();
				}
				printf("\n");
			}
		}
	}
}

0198
さいころの割に比較的まともな問題です。少なくとも0171よりはまともな問題。上面固定したら4通りまわすだけでいける。

#include<stdio.h>
char t[30][100];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++)
			for(int j=0;j<6;j++)
				scanf("%s",t[i]+j);
		int ret=0;
		for(int i=0;i<a;i++){
			bool ok=true;
			char p[4];
			p[0]=t[i][1];
			p[1]=t[i][2];
			p[2]=t[i][4];
			p[3]=t[i][3];
			char q[4];
			for(int j=0;j<i;j++){
				if(t[i][0]==t[j][0]){
					q[0]=t[j][1];
					q[1]=t[j][2];
					q[2]=t[j][4];
					q[3]=t[j][3];
				}
				if(t[i][0]==t[j][1]){
					q[0]=t[j][5];
					q[1]=t[j][2];
					q[2]=t[j][0];
					q[3]=t[j][3];
				}
				if(t[i][0]==t[j][2]){
					q[0]=t[j][5];
					q[1]=t[j][4];
					q[2]=t[j][0];
					q[3]=t[j][1];
				}
				if(t[i][0]==t[j][3]){
					q[0]=t[j][5];
					q[1]=t[j][1];
					q[2]=t[j][0];
					q[3]=t[j][4];
				}
				if(t[i][0]==t[j][4]){
					q[0]=t[j][0];
					q[1]=t[j][2];
					q[2]=t[j][5];
					q[3]=t[j][3];
				}
				if(t[i][0]==t[j][5]){
					q[0]=t[j][4];
					q[1]=t[j][2];
					q[2]=t[j][1];
					q[3]=t[j][3];
				}
				for(int k=0;k<4;k++){
					bool OK=true;
					for(int l=0;l<4;l++){
						if(p[l]!=q[(k+l)%4])OK=false;
					}
					if(OK)ok=false;
				}
			}
			if(!ok)ret++;
		}
		printf("%d\n",ret);
	}
}

構文解析で文字式が出てきたときの対処方法を考えているのですが、どうするのがいいんでしょう
(積でa*bとかが出てくると厄介、map…?)