「aoj2471～2480」の編集履歴（バックアップ）一覧はこちら

「aoj2471～2480」(2013/02/27 (水) 01:01:15) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*aoj2476 Strange Currency System
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2476
与えられた通貨を組み合わせて色々な金額を作るとき、作れない最小金額を答えよ。

解法
２４００番台の問題とは思えないほど簡単な問題です。問題が英文であること２４００番台は難しいというイメージがあっておそらく多くの人がこの問題が簡単であると気付いてないのだと思います。
通貨を小さい順にソートして小さい方から足し合わせていって作れない数字が判明したらそれが答えです。


 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<iostream>
 int main(){
 	int n;
 	scanf("%d",&n);
 	std::vector<long long int> vec;
 	long long int a,sum=0;
 	for(int i=0;i<n;i++){
 		std::cin>>a;
 		vec.push_back(a);
 	}
 	std::sort(vec.begin(),vec.end());
 	for(int i=0;i<n;i++){
 		if(sum+1<vec[i]){
 			std::cout<<sum+1<<"\n";
 			return 0;
 		}
 		sum+=vec[i];
 	}
 	std::cout<<sum+1<<"\n";
 } 

*aoj2476 Strange Currency System
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2476
与えられた通貨を組み合わせて色々な金額を作るとき、作れない最小金額を答えよ。

解法
２４００番台の問題とは思えないほど簡単な問題なのに正答者数が少ない問題です。
問題が英文であること２４００番台は難しいというイメージがあっておそらく多くの人がこの問題が簡単であると気付いてないのだと思います。
通貨を小さい順にソートして小さい方から足し合わせていって作れない数字が判明したらそれが答えです。


 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<iostream>
 int main(){
 	int n;
 	scanf("%d",&n);
 	std::vector<long long int> vec;
 	long long int a,sum=0;
 	for(int i=0;i<n;i++){
 		std::cin>>a;
 		vec.push_back(a);
 	}
 	std::sort(vec.begin(),vec.end());
 	for(int i=0;i<n;i++){
 		if(sum+1<vec[i]){
 			std::cout<<sum+1<<"\n";
 			return 0;
 		}
 		sum+=vec[i];
 	}
 	std::cout<<sum+1<<"\n";
 }