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

AOJ251～260 - (2013/02/12 (火) 19:47:04) のソース

*0256 Points for a Perfect Scorer
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0256
集計するだけの問題。
解法
一番簡単な問題なので何も考えません。

 #include<stdio.h>
 int main(){
 	int s=0,a;
 	while(scanf("%d",&a)!=EOF)s+=a;
 	printf("%d\n",s);
 } 

*0257 Railway Ticket
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0257
改札機の動きを出力する問題。

解法
一番簡単な問題なのでそのまま実装します。
Ｃでコード短さ一位の人のコードはなるほどと思います。

 #include<stdio.h>
 int main(){
 	int a,b,c;
 	scanf("%d %d %d",&a,&b,&c);
 	c=a*4+b*2+c;
 	printf("%s\n",c==4||c==2||c==0?"Close":"Open");
 }




*0258　Kitchen Garden
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0258
野菜畑の中から雑草を見つけ出す問題。

解法
エレガントな解法を考えつきませんでした。
地道に場合分けして計算してます。


 #include<stdio.h>
 #include<map>
 int main(){
 	int n,hs[102],h;
 	while(1){
 		scanf("%d",&n);
  		if(n==0)break;
 		for(int i=0;i<=n;i++)scanf("%d",&hs[i]);
 		std::map<int,int> memo;
 		std::map<int,int>::iterator it;
 		int sa;
 		for(int i=1;i<5;i++){
 			h=hs[i]-hs[i-1];
  			if(memo.find(h)==memo.end())memo[h]=0;
 			memo[h]++;
 		}
 		for(it=memo.begin();it!=memo.end();it++){
 			if((*it).second>1)sa=(*it).first;
 		}
 		if(hs[1]-hs[0]!=sa&&hs[2]-hs[1]==sa){
 			printf("%d\n",hs[0]);
 		}else{
 			for(int i=1;i<=n;i++){
 				if(hs[i]-hs[i-1]!=sa){
 					printf("%d\n",hs[i]);
 					break;
 				}
 			}
 		}
 	}
 }






*0259　All Numbers Lead to 6174
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0259
４桁の数字の各桁を大きい順から並べた数-小さい順から並べた数で更新することを繰り返すと全桁同じ数字でない場合6174に到達する。
数字が与えられるので何回の計算で到達するか答えよ。

解法
探索空間が狭いので地道に定義通り計算してもメモ化しなくても十分間に合います。
工夫点はsprintfで0で埋めるくらいです。


 #include<stdio.h>
 #include<stdlib.h>
 #include<algorithm>
 
 int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		if(n%1111==0){
 			printf("NA\n");
 			continue;
 		}
 		
 		int ans=0;
 		while(n!=6174){
 			ans++;
 			char text[10],c;
 			sprintf(text,"%04d",n);
 			std::sort(text,text+4);
 			int num1=(text[0]-'0')*1000+(text[1]-'0')*100+(text[2]-'0')*10+(text[3]-'0');
 			int num2=(text[0]-'0')+(text[1]-'0')*10+(text[2]-'0')*100+(text[3]-'0')*1000;
 			n=num2-num1;
 		}
 		printf("%d\n",ans);
 	}
 }








*260　Salary for a Plumber
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0260
パイプ屋さんの給料を最大化する問題。

解法
全部繋げた状態からどこを切っても、パイプの数は１つ増えて全体の長さは切断した箇所だけ減ります。
この状態からさらに切っても同じです。
よって一番短いジョイントから優先して切っていけば答えが出ます。
問題を見て答えを思いつくまで２日かかりました。


 #include<stdio.h>
 #include<algorithm>
 #include<iostream>
 
 unsigned int js[65001];
 int main(){
 	while(1){
 		int n;
 		scanf("%d",&n);
 		if(n==0)break;
 		unsigned int sumLen=0,p;
 		for(int i=0;i<n;i++){
 			std::cin>>p;
 			sumLen+=p;
 		}
 		for(int i=0;i<n-1;i++){
 			std::cin>>js[i];
 			sumLen+=js[i];
 		}
 		std::sort(js,js+n-1);
 		unsigned int ans=sumLen;
 		unsigned int count=2;
 		for(int i=0;i<n-1;i++){
 			sumLen-=js[i];
 			if(sumLen*count>ans)ans=sumLen*count;
 			count++;
 		}
 		std::cout<<ans<<"\n";
 	}
 }