※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

2435 Zero Division Checker

逆ポーランド記法で変数付きの式が与えられるので、変数が指定されたどの値の組み合わせになっても0除算エラーが起きないならcorrect、起きるならerrorを返せという問題。

解法
動的計画法で解きました。
式の結果はどこも0~255の範囲に定まるのでこの範囲で演算が行われるたびにあり得る演算結果の組を全部保管して次の演算へ進みます。
手元でテストデータを用意するのがめんどくさそうな問題だったので一発で通ったのはよかったよかった。
もし通らなかったらどれだけめんどくさいか考えたくもない問題だなこれ。
とりあえず通ったけどうーん本物のコンパイラはこれの100倍大変なんだよなきっと?


#include<stdio.h>
#include<stack>
#include<map>
#include<string>
#include<iostream>
#include<string.h>
#include<stdlib.h>

struct S{
	bool oks[260];
};

int main(){
	int m;
	unsigned char num1,num2;
	scanf("%d",&m);
	std::map<std::string,S> toVar;
	std::stack<std::string> st;
	std::string str,str1,str2;
	S s,s1,s2,s3;
	int d,u;
	for(int i=0;i<m;i++){
		std::cin>>str>>d>>u;
		for(int i=0;i<256;i++){
			if(d<=i&&i<=u)s.oks[i]=true;
			else s.oks[i]=false;
		}
		toVar[str]=s;
	}
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		std::cin>>str;
		if(str!="+"&&str!="-"&&str!="*"&&str!="/"){
			st.push(str);
 			continue;
		}
		str2=st.top();
		st.pop();
		str1=st.top();
		st.pop();
		int num;
		if(toVar.find(str1)==toVar.end()){
			memset(s1.oks,false,sizeof(s1.oks));
			sscanf(str1.c_str(),"%d",&num);
			s1.oks[num]=true;
		}else {
			s1=toVar[str1];
		}
		if(toVar.find(str2)==toVar.end()){
			memset(s2.oks,false,sizeof(s2.oks));
			sscanf(str2.c_str(),"%d",&num);
			s2.oks[num]=true;
 		}else {
			s2=toVar[str2];
		}
		/*
		printf("s1=");
		for(int i=0;i<20;i++){
			printf("%d ",s1.oks[i]);
 		}
		printf("\ns2=");
		for(int i=0;i<20;i++){
			printf("%d ",s2.oks[i]);
		}
		printf("\n");
		*/
		memset(s3.oks,false,sizeof(s3.oks));
		for(int j=0;j<256;j++){
			if(s1.oks[j]==false)continue;
			for(int k=0;k<256;k++){
				if(s2.oks[k]==false)continue;
				if(str=="+"){
					s3.oks[(j+k)%256]=true;
				}else if(str=="-"){
					s3.oks[(j-k+256)%256]=true;
				}else if(str=="*"){
					s3.oks[(j*k)%256]=true;
				}else if(str=="/"){
					if(k==0){
						printf("error\n");
						return 0;
					}else{
						s3.oks[(j/k)%256]=true;
					}
				}
			}
		}
		/*
		printf("s3=");
		for(int i=0;i<20;i++){
			printf("%d ",s3.oks[i]);
		}
		printf("\n\n");
		*/
		toVar[str2]=s3;
		st.push(str2);
	}
	printf("correct\n");
}



2440 Kagisys

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2440
扉の認証システムに関する問題。

解法
簡単すぎる問題なのでそのまま実装します。

#include<stdio.h>
#include<string>
#include<set>
#include<iostream>
 
int main(){
	int n,m;
	std::set<std::string> memo;
	std::string str;
	std::cin>>n;
	while(n--){
		std::cin>>str;
		memo.insert(str);
	}
	bool modeClose=true;
	std::cin>>m;
	while(m--){
		std::cin>>str;
		if(memo.find(str)==memo.end()){
			std::cout<<"Unknown ";
		}else if(modeClose==true){
			modeClose=false;
			std::cout<<"Opened by ";
		}else if(modeClose==false){
			modeClose=true;
			std::cout<<"Closed by ";
		}
		std::cout<<str<<"\n";
	}
	
}