「aoj2400~2410」の編集履歴(バックアップ)一覧に戻る

aoj2400~2410 - (2012/07/04 (水) 14:28:33) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+*2401 Equation
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401
+a~kまでのtrue falseの全組み合わせを設定してsaiki関数で再帰下降構文解析でためしています。
+恥ずかしいことに3連続でタイムリミッドの不正解を食らってしまいました。
+
+
+
+
+ #include<stdio.h>
+ bool bPerm[12],isOK;
+ bool hitSymbols[12];
+ int p;
+ bool saiki(char com[1001],bool modeRe,int deep){
+	bool b;
+	char s;
+	while(com[p]!='\0'){
+		s=com[p];
+		if(s=='\0')break;
+		p++;
+		
+		if('a'<=s&&s<='k'){
+			b=bPerm[s-'a'];
+		}else if(s=='T'){
+			b=true;
+		}else if(s=='F'){
+			b=false;
+		}else if(s=='*'){
+			b=saiki(com,true,deep+1)&&b;
+		}else if(s=='+'){
+			b=saiki(com,true,deep+1)||b;
+		}else if(s=='-'&&com[p]=='>'){
+			p++;
+			b=(saiki(com,true,deep+1)==false&&b==true)?false:true;
+		}else if(s=='-'){
+			b=!saiki(com,true,deep+1);
+		}else if(s=='('){
+			b=saiki(com,false,deep+1);
+		}else if(s==')'){
+			return b;
+		}
+		//printf("(%s %c %d)",b?"t":"f",s,deep);
+		if(modeRe==true){
+			return b;
+		}
+	}
+	return b;
+ }
+ void saiki1(char comL[1001],char comR[1001],int deep){
+	if(deep==11){
+		p=0;
+		bool b1=saiki(comL,false,0);
+		p=0;
+		//printf("\n\n");
+		bool b2=saiki(comR,false,0);
+		//printf("<%s %s>\n",b1?"t":"f",b2?"t":"f");
+		if(b1!=b2)isOK=false;
+		//isOK=false;
+	}else{
+		bPerm[deep]=true;
+		if(isOK==false)return;
+		saiki1(comL,comR,deep+1);
+		if(isOK==false)return;
+		if(hitSymbols[deep]==false)return;
+		bPerm[deep]=false;
+		saiki1(comL,comR,deep+1);
+	}
+ }
+ bool calc(){
+	char comL[1001],comR[1001],c1,c2;
+	scanf("%[^=#]%c",comL,&c1);
+	if(c1=='#')return false;
+	scanf("%s%c",comR,&c2);
+	isOK=true;
+	//printf("<%s>=<%s>",comL,comR);
+	//出現文字の種類を網羅する
+	for(int i=0;i<12;i++)hitSymbols[i]=false;
+	for(int i=0;comL[i]!='\0';i++){
+		char c=comL[i];
+		if('a'<=c&&c<='k'){
+			hitSymbols[c-'a']=true;
+		}
+	}
+	for(int i=0;comR[i]!='\0';i++){
+		char c=comR[i];
+		if('a'<=c&&c<='k'){
+			hitSymbols[c-'a']=true;
+		}
+	}	
+	saiki1(comL,comR,0);
+	printf("%s\n",isOK==true?"YES":"NO");
+	return true;
+ }
+ int main(){
+	while(calc());
+ }
+
+
+
+
 *2400 You Are the Judge
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2400
 
 なにやら知らないうちに2400番台の問題が追加されていた。
 もちろん記念すべき1問目は伝統にのっとり肩慣らしの簡単問題である。
 こんな簡単な問題でコード実行速度差が出てくるというのが何とも不思議である。
 どうやったらこの問題を遅く実行できるのか想像がつかない。
 
 
  #include <stdio.h>
  #include <algorithm>
  #include <vector>
  struct team{
 	int a,b[11],no,p;//正答数、誤答数
 	bool operator<(const team& t)const{
 		if(a!=t.a)return a>t.a;
 		if(p!=t.p)return p<t.p;
 		return no<t.no;
 	}
 	team(){
 		for(int i=0;i<11;i++)b[i]=0;
 		a=p=0;
 	}
  };
  void calc(int t,int p,int r){
 	std::vector<team> teams;
 	team t1;
 	for(int i=0;i<t;i++){
 		t1.no=i+1;
 		teams.push_back(t1);
 	}
 	int tID,pID,time;
 	char com[20];
 	for(int i=0;i<r;i++){
 		scanf("%d %d %d %s",&tID,&pID,&time,com);
 		tID--;
 		if(com[0]=='C'){
 			teams[tID].a++;
 			teams[tID].p+=1200*teams[tID].b[pID]+time;
 		}else{
 			teams[tID].b[pID]++;
 		}
 	}
 	std::sort(teams.begin(),teams.end());	
 	for(int i=0;i<t;i++){
 		printf("%d %d %d\n",teams[i].no,teams[i].a,teams[i].p);
 	}
  }
  int main(){
 	int t,p,r;
 	while(1){
 		scanf("%d %d %d",&t,&p,&r);
 		if(t==0&&p==0&&r==0)break;
 		calc(t,p,r);
 	}
  }