「aoj2431～2440」の編集履歴（バックアップ）一覧に戻る

aoj2431～2440 - (2013/01/20 (日) 11:53:29) のソース

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

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


 #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";
 	}
 	
 }