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

問41 Expression

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
4つの1~9までの数字を読み込んで、それに+ - *()を使って10を作れという問題。

解法
Prolog言語で考えてそれを無理やりC++に翻訳して解いてみた。
要は全組み合わせを検証している。
  • +と*は交換法則で少し計算量を低減。
  • 大学行ったことないのでこの我流の方法がよいのかはよくわからないまあ合格できてるからいいかな

#include<stdio.h>
#include<string>
#include<algorithm>
#include<set>
struct S{
 	int num;
	std::string siki;
	bool spents[4];
	bool calcOK(const S& s){
		for(int i=0;i<4;i++){
			if((s.spents[i]==true)&&(spents[i]==true))return false;
		}
		return true;
 	}
	bool operator<(const S& s1)const{
		for(int i=0;i<4;i++){
			if(spents[i]!=s1.spents[i])return spents[i]<s1.spents[i];
		}
		return num<s1.num;
	}
};

std::set<S> sets[5];

S unionSpents(S& s1,S& s2){
	S s3;
	for(int i=0;i<4;i++){
		s3.spents[i]=(s1.spents[i] || s2.spents[i]);
	}
	return s3;
}
S add(S& s1,S& s2){
	S s3=unionSpents(s1,s2);
	s3.siki="(" + s1.siki + " + " + s2.siki + ")";
	s3.num=s1.num+s2.num;
	return s3;
}

S dell(S& s1,S& s2){
	S s3=unionSpents(s1,s2);
	s3.siki="(" + s1.siki + " - " + s2.siki +")";
	s3.num=s1.num-s2.num;
	return s3;
}

S mult(S& s1,S& s2){
	S s3=unionSpents(s1,s2);
	s3.siki="(" + s1.siki + " * " + s2.siki +")";
	s3.num=s1.num*s2.num;
	return s3;
}
 

void search(int nums[4],int size){
	if(size==1){
		for(int i=0;i<4;i++){
			S s1;
			s1.num=nums[i];
			s1.siki=(char)(nums[i]+'0');
 			for(int j=0;j<4;j++){
				s1.spents[j]=(i==j)?true:false;
			}
			sets[1].insert(s1);
		}
	}else if(size>1){
		search(nums,size-1);
		for(int i=1;i<=size;i++){
			S s1,s2;
 			int j=size-i;
			if(j<1)continue;
			std::set<S>::iterator it1,it2;
			for(it1=sets[i].begin();it1!=sets[i].end();it1++){
				s1=(*it1);
				for(it2=sets[j].begin();it2!=sets[j].end();it2++){
 					s2=(*it2);
					if(s1.calcOK(s2)){
						if(i<=j)sets[size].insert(add(s1,s2));
						sets[size].insert(dell(s1,s2));
						if(i<=j)sets[size].insert(mult(s1,s2));
					}
 				}
			}
		}
	}
}

bool isOK10(S& s1){
	return (s1.num==10)&&s1.spents[0]&&s1.spents[1]&&s1.spents[2]&&s1.spents[3];
} 
void calc(int ns[4]){
	sets[1].clear();
 	sets[2].clear();
	sets[3].clear();
	sets[4].clear();
	search(ns,4);
	S s1;
	for(std::set<S>::iterator it=sets[4].begin();it!=sets[4].end();it++){
		s1=(*it);
		if(isOK10(s1)){
			printf("%s\n",s1.siki.c_str());
			return ;
 		}
	}
	printf("0\n");
}


int main(){
	int ns[4];
 	while(1){
		scanf("%d %d %d %d",&ns[0],&ns[1],&ns[2],&ns[3]);
		if((ns[0]|ns[1]|ns[2]|ns[3])==0)break;
 		calc(ns);
	}
}




問42 A Thief

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042
泥棒が風呂敷にお宝を包む問題。
解法
ナップザック問題そのままです。


#include<stdio.h>
 
int main(){
int W,caseNo=1;
	
	while(scanf("%d",&W)!=EOF){
		if(W==0)break;
		int memo[1001]={0},sum=0,n,wi,vi;
		scanf("%d",&n);
 		while(n--){
			scanf("%d,%d",&vi,&wi);
			sum+=wi;
			if(sum>W)sum=W;
			for(int i=sum;i>=wi;i--){
				if(i-wi>0&&memo[i-wi]==0)continue;
				if(memo[i]<memo[i-wi]+vi)memo[i]=memo[i-wi]+vi;
			}
		}
		int ansV=0,ansW=0;
		for(int i=0;i<=W;i++){
			if(ansV<memo[i]){
				ansV=memo[i];
				ansW=i;
			}
		}
		printf("Case %d:\n%d\n%d\n",caseNo,ansV,ansW);
		caseNo++;
	}
}



43 Puzzle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0043
与えられ13個の数字に一つ足して役を作れるか判定する問題。

全部の数を使い切るのですから、小さい数からためし、その数を使い切るまで2,3、3連続組を作りあとは全探索するだけです。
手前からデータを食べていくリストプロセッサー的な発想です。
データ数が多い場合上がれる役のすべてをstd::setに入れてそれと照合するという発想もありかもしれません。


#include<stdio.h>
#include<string.h>
 
bool search(int count[10],int p,bool isTwoCreate){
 	bool result=false;
if(p==10&&isTwoCreate){
		return true;
 	}else{
		if(isTwoCreate==false){
		count[p]-=2;
			result=result || search(count,p,true);
			count[p]+=2;
 		}
	if(count[p]>2){
			count[p]-=3;
 			result = result || search(count,p,isTwoCreate);
			count[p]+=3;
		}
		if(p<=7&&count[p]>0&&count[p+1]>0&&count[p+2]>0){
			count[p]--;
			count[p+1]--;
 			count[p+2]--;
			result=result || search(count,p,isTwoCreate);
			count[p]++;
		count[p+1]++;
 			count[p+2]++;
		}
		if(count[p]==0){
			result=result || search(count,p+1,isTwoCreate);
		}
 		
	}
	return result;
}

int main(){
	char text[15];
	while(scanf("%s",text)!=EOF){
		int count[10]={0};
 		for(int i=0;text[i]!='\0';i++)count[text[i]-'0']++;
		bool isFirst=true;
		bool isOK=true;
		for(int i=1;i<=9;i++)if(count[i]>=5)isOK=false;
		for(int i=1;isOK && i<=9;i++){
 			if(count[i]<4){
				count[i]++;
				if(search(count,0,false)){
					isFirst?isFirst=false:printf(" ");
 					printf("%d",i);
				}
				count[i]--;
			}
 		}
		printf("%s",isFirst?"0\n":"\n");
	}
}




問44 Prime Number II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044
与えられた数の上下直近にある素数二つをこたえる問題。

篩を使ってあとは上下を探すだけです。


#include<stdio.h>
#include<string.h>
const int MAX=60000;
bool isPrime[MAX+1];

void calc(){
	memset(isPrime,true,sizeof(isPrime));
	isPrime[0]=isPrime[1]=false;
	for(int i=2;i*i<=MAX;i+=(1+(i&1))){
		if(isPrime[i]==false)continue;
		int add=i%2==0?i:i*2;
		for(int j=(i%2==0?i*2:i*3);j<=MAX;j+=add){
 			isPrime[j]=false;
		}
	}
}

int main(){
	calc();
	int n;
	while(scanf("%d",&n)!=EOF){
		int p1,p2;
		for(p1=n-1;isPrime[p1]==false;p1--);
 		for(p2=n+1;isPrime[p2]==false;p2++);
		printf("%d %d\n",p1,p2);
	}
}



問45 Sum and Average

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0045
販売金額と販売数量の平均を出す問題

簡単なので特に工夫するところないです。
0.5足してintをとるくらいですね。

#include<stdio.h>
int main(){
	double v,n,sum=0,count=0,type=0;
	while(scanf("%lf,%lf",&v,&n)!=EOF){
 		sum+=v*n;
		count+=n;
		type+=1;
 	}
	printf("%.0lf\n%d\n",sum,(int)(count/type+0.5));
}