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

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

AOJ41~50 - (2011/08/12 (金) 09:07:40) のソース

*41 Expression
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
難しそうなのでパス。
丁寧に場合分けしたらいいのだろうか?




----
*0042 A Thief
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042
典型的なナップザック問題、メモ化探索で計算。
計算量が小さいのでメモ化も適当。
メモは大きい方から足しこむことで、同じ荷物を何度も入れることを防いでいる。
もう少し賢いコードがありそうだけど?


 #include<stdio.h>
void calc(int max,int i){
	int memo[1001]={0},n,v,w,tMax,ansV=0,ansW=0;
	
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d,%d",&v,&w);
		for(int j=max;j>=w;j--){
			if((j==w || memo[j-w]>0) && memo[j]<memo[j-w]+v){
					memo[j]=memo[j-w]+v;
			}
		}
	}
	for(int i=0;i<=max;i++){
		if(memo[i]>ansV){
			ansV=memo[i];
			ansW=i;
		}
	}
	
	printf("Case %d:\n",i);
	printf("%d\n%d\n",ansV,ansW);
}

int main(){
	int w,i=1;
	scanf("%d",&w);
	while(w!=0){
		calc(w,i);
		i++;
		scanf("%d",&w);
	}
}








----
*0043 Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0043
計算量が小さいので力づくで全探索。
行列演算で解けそうだけど、どう行列に落とし込めばいいかわからなかったので探索で解いた。
もう少し賢いコードがありそう。

 #include<stdio.h>
bool ans,first;
int  m[10];

void saiki(int deep){
	if(deep==4){
		for(int i=1;i<10;i++){
			if(m[i]==2){
				ans=true;
				break;
			}
		}
		return ;
	}
	for(int i=1;i<10;i++){
		if(m[i]>2){
			m[i]-=3;
			saiki(deep+1);
			m[i]+=3;
			if(ans==true) return;
		}
	}
	for(int i=1;i<8;i++){
		if(m[i]>0 && m[i+1]>0 && m[i+2]>0){
			m[i]--;
			m[i+1]--;
			m[i+2]--;
			saiki(deep+1);
			m[i]++;
			m[i+1]++;
			m[i+2]++;
			if(ans==true) return;
		}
	}
	
}

int main(){
	char t[14];
	
	while(scanf("%s",t)>0){
		for(int i=1;i<10;i++)m[i]=0;
		for(int i=0;i<13;i++)m[t[i]-'0']++;
		first=true;
		for(int i=1;i<10;i++){
			ans=false;
			if(m[i]<4){
				m[i]++;
				saiki(0);
				m[i]--;
				if(ans==true){
					if(first==true){
						printf("%d",i);
						first=false;
					}else{
						printf(" %d",i);
					}
				}
			}
		}
		if(first==true){
			printf("0");
		}
		printf("\n");
	}
}









----
*0044 Prime Number II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044
素数を求めて、setに入れてupper_boundとlower_boundで求めるだけ。
もしnが50000よりずっと大きな数になったらどうするか考えものの問題。

#include<stdio.h>
#include<set>
std::set<int> s;

void setSo(){
	int so[50023]={0};
	
	s.insert(2);
	for(int i=3;i<50023;i+=2){
		if(so[i]!=0) continue;
		s.insert(i);
		for(int j=i*3;j<50023;j+=i*2){
			so[j]=1;
		}
	}
}

int main(){
	setSo();
	int n;
	while(scanf("%d",&n)>0){
		printf("%d %d\n",*(--s.lower_bound(n)),*(s.upper_bound(n)));
	}
}






----
*0045 Sum and Average
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0045
何も考えずに足しこむだけ。
#include<stdio.h>
int main(){
	int m,t,s=0,i=0;
	double c=0;
	while(scanf("%d,%d",&m,&t)>0){
		s+=m*t;
		c+=t;
		i++;
	}
	printf("%d\n%d\n",s,(int)(c/i+0.5));
}





----
*0046 Differential
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0046
一番大きいのと小さいのをメモして差分をとるだけ。
#include<stdio.h>
int main(){
	double max,min,t;
	scanf("%lf",&max);
	min=max;
	while(scanf("%lf",&t)!=EOF){
		min=min>t?t:min;
		max=max<t?t:max;
	}
	printf("%lf\n",max-min);
}








----
*0047 Cup Game
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0047
今ボールのはいってるカップが交換されたらボールの位置を交換するだけ。
3項演算子?がコード短縮のポイント。
コードの短さでは結構自信があったのだがを半分の短さのコードで書けるらしい、、、ちょっと想像がつかない。


 #include <stdio.h>
int main(void)
{
	char n='A',a,b;
	while(scanf("%c,%c",&a,&b)!=EOF){
		n=n==a?b:n==b?a:n;
	}
	printf("%c\n",n);
}



----
*0048 Class
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0048
簡単な問題なので愚直に実装。
if文で分岐してもよかったかも。
体重分岐の部分を?演算子を何個も連ねる解法もあり少し面白い。

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

int main(){
	std::map<double,std::string> c;
	std::map<double,std::string>::iterator it;
	c[48.0]="fly";
	c[51.0]="bantam";
	c[54.0]="feather";
	c[57.0]="light";
	c[60.0]="light welter";
	c[64.0]="welter";
	c[69.0]="light middle";
	c[75.0]="middle";
	c[81.0]="light heavy";
	double w;
	while(scanf("%lf",&w)!=EOF){
		if(w<=48.0){
			printf("light fly\n");
		}else if(w>91.0){
			printf("heavy\n");
		}else{
			it=c.lower_bound(w);
			if(c.begin()!=it) it--;
			printf("%s\n",(*it).second.c_str());
		}
	}
}







----
*0049 Blood Groups
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0049
簡単な問題なので一番楽な方法で実装。
もう少しコード削れたかな?

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

int main(){
	std::map<std::string,int> memo;
	int s;
	char d[3];
	memo["A"]=memo["B"]=memo["AB"]=memo["O"]=0;
	while(scanf("%d,%s",&s,d)!=EOF){
		memo[d]++;
	}
	printf("%d\n%d\n%d\n%d\n",memo["A"],memo["B"],memo["AB"],memo["O"]);
}





----
*0050 Apple and Peach
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0050
文字数が同じことを利用して手抜き実装、適当です。

#include <iostream>
#include<string>
int main(){
	std::string s;
	std::string t;
	getline(std::cin,s);
	int len=s.size();
	for(int i=0;i<len-4;i++){
		if(s[i]=='a' || s[i]=='p'){
			t=s.substr(i,5);
			if(t=="apple"){
				s.replace(i,5,"peach");
			}else if(t=="peach"){
				s.replace(i,5,"apple");
			}
		}
	}
	std::cout<<s;
}