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

AOJ41~50 - (2011/08/12 (金) 08:59:02) の編集履歴(バックアップ)


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よりずっと大きな数になったらどうするか考えものの問題。

<stdio.h>
<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
何も考えずに足しこむだけ。
<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
一番大きいのと小さいのをメモして差分をとるだけ。
<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);
}