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
解法
簡単すぎる問題なのでそのまま実装します。
#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";
}
}
最終更新:2013年01月20日 11:53