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

問106 Discounts of Buckwheat


解法
200グラム 380円
1000グラム1520円
300グラム 550円
1200グラム 1870円
500グラム 850円
1500グラム 2244円
の商品があるのだと考えて動的計画法を適用すればきれいに解けます。

#include<stdio.h> 
int main(){
	int gs[6]={2,10,3,12,5,15};
	int vs[6]={380,1520,550,1870,850,2244};
 	int dp[51]={0};
	for(int i=0;i<6;i++){
		int g=gs[i];
		int v=vs[i];
		for(int j=0;j+g<=50;j++){
			if(j>0&&dp[j]==0)continue;
			if(dp[j+g]==0||dp[j+g]>=dp[j]+v){
 				dp[j+g]=dp[j]+v;
			}
		}
	}
	int g;
	while(scanf("%d",&g)!=EOF){
		if(g==0)break;
 		printf("%d\n",dp[g/100]);
	}
}



問107 Carry a Cheese

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0107
直方体のチーズが円形の穴を通るか判定する問題

解法
直方体の四角形の一番短い対角線が円の直径よりも小さいならチーズは穴を通ります。
これをきちんと証明するのは少し難しいですが直感的には明らかだと思います。

#include<stdio.h>
#include<algorithm>
int main(){
	int a,b,c,n,t,r;
	while(1){
		scanf("%d %d %d",&a,&b,&c);
 		if((a|b|c)==0)break;
		t=std::max(a,std::max(b,c));
		t=a*a+b*b+c*c-t*t;
		scanf("%d",&n);
		while(n--){
 			scanf("%d",&r);
			printf("%s\n",t<4*r*r?"OK":"NA");
		}
	}
}




問108 Operation of Frequency of Appearance


解法
そのまま実装。
再帰万歳(太陽万歳)。
最初の数字を除けば12以下の数しかならばいないんだからこのへんstd::mapを使わない理由はあるのだけれど。
それに対応するとコードが膨らむので対処はしない。


#include<stdio.h>
#include<map>
#include<string.h>
int calcNext(int nums[12],int n,int deep,int reNums[12]){
	std::map<int,int> memo;
	for(int i=0;i<n;i++){
		int num=nums[i];
		if(memo.find(num)==memo.end())memo[num]=0;
		memo[num]++;
	}
	int next[12];
	for(int i=0;i<n;i++)next[i]=memo[nums[i]];
	bool isLast=true;
	for(int i=0;i<n;i++){
		if(next[i]!=nums[i])isLast=false;
	}
 	if(isLast==true){
		memcpy(reNums,next,sizeof(next));
		return deep;
	}else{
		return calcNext(next,n,deep+1,reNums);
	}
}

int main(){
 	int n,nums[12],ans[12];
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<n;i++)scanf("%d",&nums[i]);
		printf("%d\n",calcNext(nums,n,0,ans));
		for(int i=0;i<n;i++){
			if(i>0)printf(" ");
			printf("%d",ans[i]);
 		}
		printf("\n");
	}
}





問109 Smart Calculator

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109
与えられた四則演算の式を計算する問題。
解法
再帰下降構文解析、私にとって書きやすい方法で書いてみたので参考にしてはいけない。
http://d.hatena.ne.jp/nanikaka/20110829/1314603165
この人みたいに関数の粒度を細かくするのが正しいらしい。

#include<stdio.h>
#include<ctype.h>
int ope(int& p,char *siki,int pri,int deep){
	bool first=true;
	int num=0;
	char c=siki[p];
	while(c!='='&&c!='\0'){
		c=siki[p];
		if(c=='('){
			p++;
			num=ope(p,siki,0,deep+1);
			p++;
		}
		if(c==')'){
			return num;
		}
		if(c=='-'&&first==true){
			num=0;
			while(isdigit(siki[p+1])){
				num=num*10+siki[p+1]-'0';
				p++;
			}
			num=-num;
			p++;
		}
		if(c=='+'){
 			if(1<=pri){
				return num;
		}else{
 				p++;
				num+=ope(p,siki,1,deep+1);
			}
		}

		if(c=='-'&&first==false){
			if(1<=pri){	
				return num;
			}else{
				p++;
				num-=ope(p,siki,1,deep+1);
			}
		}
		if(c=='*'){
			if(2<=pri){
				return num;
			}else{
 				p++;
				num*=ope(p,siki,2,deep+1);
			}
		}
		if(c=='/'){
			if(2<=pri){
				return num;
		}else{
				p++;
				num/=ope(p,siki,2,deep+1);
			}
		}
		if(isdigit(c)){
			num=c-'0';
			while(isdigit(siki[p+1])){
				num=num*10+siki[p+1]-'0';
				p++;
			}
			p++;
		}
		first=false;
 	}
	return num;
}

int main(){
	int n;
	char siki[101];
	scanf("%d",&n);
 	while(n--){
		scanf("%s",siki);
		int p=0;
		printf("%d\n",ope(p,siki,0,0));
	}
}





問110 Alphametic

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0110
簡単な覆面残を試す問題
解法
数字を文字列としてみてXを一つずつ数字を代入して
小学生の足し算の要領で足していって試すだけです。


#include<stdio.h>
#include<string.h>
#include<algorithm>

bool isAddOK(char* L1,char* M1,char* R1){
 	int pL=strlen(L1)-1;
	int pM=strlen(M1)-1;
	int pR=0;
	char add=0,numL,numM,T;
	char tempR[255];
	while(add!=0||0<=pL||0<=pM){
		numL=pL<0?0:L1[pL]-'0';
		numM=pM<0?0:M1[pM]-'0';
		T=numL+numM+add;
 		tempR[pR]=T%10+'0';
		add=T/10;
		pR++;
		pL--;
		pM--;
	}
	tempR[pR]='\0';
	std::reverse(tempR,tempR+pR);
	return strcmp(R1,tempR)==0;
}

void changeX(char* nums,char* reNums,char c){
	for(int i=0;i<=strlen(nums);i++){
		if(nums[i]=='X')reNums[i]=c;
 		else reNums[i]=nums[i];
	}
}

int main(){
	char L[255],M[255],R[255],L1[255],M1[255],R1[255];
	while(scanf("%[^+]%*c%[^=]%*c%[^\n]%*c",L,M,R)!=EOF){
		bool hit=false;
		for(char i='0';i<='9';i++){
 			if(i=='0' && L[0]=='0' && strlen(L)>1)continue;
			if(i=='0' && M[0]=='0' && strlen(M)>1)continue;
			if(i=='0' && R[0]=='0' && strlen(R)>1)continue;
			changeX(L,L1,i);
			changeX(M,M1,i);
			changeX(R,R1,i);
			if(isAddOK(L1,M1,R1)){
				printf("%c\n",i);
				hit=true;
			}
		}
		if(hit==false)printf("NA\n");
	}
}