「AOJ191～200」の編集履歴（バックアップ）一覧に戻る

AOJ191～200 - (2011/08/30 (火) 18:20:19) のソース

*0191　Baby Tree
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0191
植物に色々な種類の肥料をやって、一番成長する肥料のやり方とその時できる植物のサイズをこたえる問題。

解法
動的計画法で各ターンごとに計算していくだけです。


 #include<stdio.h>
 #include<string.h>
 double fertilizer[102][102];
 void calc(int n,int m){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			scanf("%lf",&fertilizer[i][j]);
		}
	}
	double memo[2][101];
	for(int i=0;i<n;i++){
		memo[0][i]=1.0;
	}
	
	int now,next=0;
	double size,nextSize;
	for(int i=0;i<m-1;i++){
		now=i%2;
		next=(i+1)%2;
		for(int j=0;j<n;j++){
			memo[next][j]=0;
		}
		for(int j=0;j<n;j++){
			size=memo[now][j];
			for(int k=0;k<n;k++){
				nextSize=size*fertilizer[j][k];
				if(memo[next][k]<nextSize){
					memo[next][k]=nextSize;
				}
			}
		}
	}
	double ans=0;
	for(int i=0;i<n;i++){
		ans=memo[next][i]>ans?memo[next][i]:ans;
	}
	printf("%.2lf\n",ans);
 }
 int main(){
	int n,m;
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0 && m==0) break;
		calc(n,m);
	}
 }






----
*0195　What is the Most Popular Shop in Tokaichi?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0195
売上げ記録から一番売り上げのいい店を求める問題です。
解法
計算して最高値を保存するだけです。

 #include<stdio.h>
 int main(){
	int s1,s2,ans,no,i;
	while(1){
		scanf("%d %d",&s1,&s2);
		ans=s1+s2;
		if(ans==0)break;
		no=0;
		for(i=1;i<5;i++){
			scanf("%d %d",&s1,&s2);
			if(ans<s1+s2){
				ans=s1+s2;
				no=i;
			}
		}
		printf("%c %d\n",no+'A',ans);
	}
 }






----
*0196　Baseball Championship
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0196
ベースボールの戦績表を元に上位のチームから出力する問題。

解法
チーム構造体を定義してソート基準を指定するだけです。
これくらい簡単な作業ならＥｘｃelで十分です。



 #include<stdio.h>
 #include <algorithm>
 struct team{
	int v,l,no;
	char name;
	bool operator<(const team t)const{
		if(v!=t.v) return v>t.v;
		if(l!=t.l) return l<t.l;
		return no<t.no;
	}
 };
 void setTeam(int n){
	team teams[11];
	int t;
	for(int i=0;i<n;i++){
		scanf(" %c",&teams[i].name);
		teams[i].v=teams[i].l=0;
		teams[i].no=i;
		for(int j=1;j<n;j++){
			scanf("%d",&t);
			if(t==0)teams[i].v++;
			if(t==1)teams[i].l++;
		}
	}
	std::sort(teams,teams+n);
	for(int i=0;i<n;i++){
		printf("%c\n",teams[i].name);
	}
 }
 int main(){
	int n;
	while(scanf("%d",&n),n>0){
		setTeam(n);
	}
 }