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

「AOJ581～590」(2013/04/05 (金) 12:43:53) の最新版変更点

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

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

*0582 Triangle Types
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0582
三角形のデータが与えられるのでそれが三角形をなすなら、鈍角三角形か直角か鋭角か判断してカウントし最後にその数を出力せよ。

解法
中学校で習った三角形の公式通りに判定するだけです。


 #include<stdio.h>
 #include<algorithm>
 int main(){
  	int as[3],ans[3]={0};
 	while(1){
 		scanf("%d %d %d",&as[0],&as[1],&as[2]);
 		std::sort(as,as+3);
 		if(as[0]+as[1]<=as[2])break;
 		int len =as[0]*as[0]+as[1]*as[1];
 		int len2=as[2]*as[2];
 		if(len==len2){
  			ans[0]++;
 		}else if(len>len2){
 			ans[1]++;
 		}else{
 			ans[2]++;
 		}
 	}
 	printf("%d %d %d %d\n",ans[0]+ans[1]+ans[2],ans[0],ans[1],ans[2]);
 }








*0583 Common Divisors
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0583
2つか３つの数が与えられるのでその数の公約数を小さい順に表示する問題。

解法
最初素因数分解してとめんどくさい方法を考えましたが、値の範囲が10＾8と小さいことをりようして手抜きで解きました。
一番小さい数limitを選び√limitまでの数で試し割します。
as[j]/iが割り切れるならas[j]/iとiを割る候補として保管。
最後に小さい方から試し割していけばいいだけです。


 #include<stdio.h>
 #include<set>
 #include<map>
 #include<algorithm>
 int main(){
  	int n,as[3];
 	scanf("%d",&n);
 	std::set<int> ans;
 	int limit;
 	if(n==2){
 		scanf("%d %d",&as[0],&as[1]);
 		limit=std::min(as[0],as[1]);
 	}else{
 		scanf("%d %d %d",&as[0],&as[1],&as[2]);
 		limit=std::min(std::min(as[0],as[1]),as[2]);
 	}
  	for(int i=1;i*i<=limit;i++){
 		for(int j=0;j<n;j++){
 			if(as[j]%i==0){
 				ans.insert(as[j]/i);
 				ans.insert(i);
 			}
 		}
 
	}
  	for(std::set<int>::iterator it=ans.begin();it!=ans.end();it++){
 		int num=(*it);
 		bool ok=true;
 		for(int i=0;i<n;i++)if(as[i]%num!=0)ok=false;
 		if(ok==true)printf("%d\n",num);
 	}
 }




*aoj0585 Nearest Two Points
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0585
1億個の点が平面上に散らばっている、一番近い２点の距離の２乗を求めよという問題。

解法
左端から右端へ精査していけば答えが出ます。
ある点とそれより左にある点を比べる場合、ｙ座標が同じならｘが一番大きな点とだけ比較します。
これを繰り返せば答えが出ます。
一応2013/2/18現在コードの短さ、コードの速さで一位を取ってます。
まあそのうち抜かれるでしょうが一時的に一位を取れたのは嬉しい限りです。


 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<math.h>
 
 struct P{
 	int x,y;
 	bool operator<(const P& p)const{
 		if(x!=p.x)return x<p.x;
 		return y<p.y;
 	}
 };
 std::vector<P> nums;
 
 int main(){
 	int yToX[20010];
	for(int i=0;i<20010;i++)yToX[i]=-20000;
  	std::vector<P> points;
 	P p;
 	int n;
	scanf("%d",&n);
 	for(int i=0;i<n;i++){
 		scanf("%d %d",&p.x,&p.y);
 		p.y+=10000;
 		points.push_back(p);
 	}
 	std::sort(points.begin(),points.end());
 	int ans=20*10000*10000;
 	int len=sqrt(ans);
 	for(int i=0;i<n;i++){
 		p=points[i];
 		int top=len+p.y+2;
 		int down=p.y-2-len;
 		if(top>=20000)top=20000;
 		if(down<=0)down=0;
 		for(int i=top;i>=down;i--){
 			if(yToX[i]<-10000)continue;
 			int t=(p.y-i)*(p.y-i)+(p.x-yToX[i])*(p.x-yToX[i]);
 			if(ans>t){
 				ans=t;
 				len=sqrt(ans);
 			}
 		}
 		yToX[p.y]=p.x;
 	}
 	printf("%d\n",ans);
 }



*aoj0588　Simple Calculator
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0588
優先順位のない式で四則演算を行う問題。

解法
手前から順番に読み込んで処理するだけです。

 #include<stdio.h>
 
 int main(){
 	int ans,a;
 	char t[3]=" ";
 	scanf("%d",&ans);
 	while(1){
 		scanf("%s",t);
 		if(t[0]=='=')break;
 		scanf("%d",&a);
 		if(t[0]=='+')ans+=a;
 		if(t[0]=='-')ans-=a;
 		if(t[0]=='*')ans*=a;
 		if(t[0]=='/')ans/=a;
 	}
 	printf("%d\n",ans);
 }




*aoj0589　Production
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0589
工場の生産記録から各製品の製造数を答える問題。


解法
std::stringをそのまま使うと辞書順になるので構造体でラップし直して後はstd::mapで集計して終わりです。

 #include<stdio.h>
 #include<string>
 #include<map>
 
 struct Goods{
 	std::string name;
 	bool operator<(const Goods& g)const{
 		if(name.size()!=g.name.size())return name.size()<g.name.size();
 		return name<g.name;
 	}
 };
 
 int main(){
 	int n,m;
	char name[10];
  	std::map<Goods,int> ans;
	Goods g;
  	scanf("%d",&n);
 	for(int i=0;i<n;i++){
 		scanf("%s %d",name,&m);
 		g.name=name;
 		if(ans.find(g)==ans.end())ans[g]=0;
 		ans[g]+=m;
 	}
 	for(std::map<Goods,int>::iterator it=ans.begin();it!=ans.end();it++){
 		printf("%s %d\n",(*it).first.name.c_str(),(*it).second);
 	}
 }



*aoj0590 Available Areas
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0590
与えられた自然数が、2xy+x+y x>0,y>0　ｘ、ｙは自然数として表現できるか判別する問題。

解法
yを決定すると面積をｓとして
a=(s-y)/(2y+1)が自然数になれば答えが存在します。
式の対称性から考えてa>=yの間だけ計算すれば十分なようです。

 #include<stdio.h>
 #include<iostream>
 int main(){
 	int n,ans=0;
  	scanf("%d",&n);
 	int y,s;
 	for(int i=0;i<n;i++){
 		scanf("%d",&s);
 		bool ok=false;
 		for(y=1;(2*y+1)<=s-y;y++){
 			if((s-y)%(2*y+1)==0){
 				ok=true;
  				break;
 			}
 			int t=(s-y)/(2*y+1);
 			if(t<y)break;
 		}
 		ans+=(ok==false);
 	}
 	printf("%d\n",ans);
 }

*0582 Triangle Types
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0582
三角形のデータが与えられるのでそれが三角形をなすなら、鈍角三角形か直角か鋭角か判断してカウントし最後にその数を出力せよ。

解法
中学校で習った三角形の公式通りに判定するだけです。


 #include<stdio.h>
 #include<algorithm>
 int main(){
  	int as[3],ans[3]={0};
 	while(1){
 		scanf("%d %d %d",&as[0],&as[1],&as[2]);
 		std::sort(as,as+3);
 		if(as[0]+as[1]<=as[2])break;
 		int len =as[0]*as[0]+as[1]*as[1];
 		int len2=as[2]*as[2];
 		if(len==len2){
  			ans[0]++;
 		}else if(len>len2){
 			ans[1]++;
 		}else{
 			ans[2]++;
 		}
 	}
 	printf("%d %d %d %d\n",ans[0]+ans[1]+ans[2],ans[0],ans[1],ans[2]);
 }








*0583 Common Divisors
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0583
2つか３つの数が与えられるのでその数の公約数を小さい順に表示する問題。

解法
最初素因数分解してとめんどくさい方法を考えましたが、値の範囲が10＾8と小さいことをりようして手抜きで解きました。
一番小さい数limitを選び√limitまでの数で試し割します。
as[j]/iが割り切れるならas[j]/iとiを割る候補として保管。
最後に小さい方から試し割していけばいいだけです。


 #include<stdio.h>
 #include<set>
 #include<map>
 #include<algorithm>
 int main(){
  	int n,as[3];
 	scanf("%d",&n);
 	std::set<int> ans;
 	int limit;
 	if(n==2){
 		scanf("%d %d",&as[0],&as[1]);
 		limit=std::min(as[0],as[1]);
 	}else{
 		scanf("%d %d %d",&as[0],&as[1],&as[2]);
 		limit=std::min(std::min(as[0],as[1]),as[2]);
 	}
  	for(int i=1;i*i<=limit;i++){
 		for(int j=0;j<n;j++){
 			if(as[j]%i==0){
 				ans.insert(as[j]/i);
 				ans.insert(i);
 			}
 		}
 
	}
  	for(std::set<int>::iterator it=ans.begin();it!=ans.end();it++){
 		int num=(*it);
 		bool ok=true;
 		for(int i=0;i<n;i++)if(as[i]%num!=0)ok=false;
 		if(ok==true)printf("%d\n",num);
 	}
 }




*aoj0585 Nearest Two Points
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0585
1億個の点が平面上に散らばっている、一番近い２点の距離の２乗を求めよという問題。

解法
左端から右端へ精査していけば答えが出ます。
ある点とそれより左にある点を比べる場合、ｙ座標が同じならｘが一番大きな点とだけ比較します。
これを繰り返せば答えが出ます。
一応2013/2/18現在コードの短さ、コードの速さで一位を取ってます。
まあそのうち抜かれるでしょうが一時的に一位を取れたのは嬉しい限りです。


 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<math.h>
 
 struct P{
 	int x,y;
 	bool operator<(const P& p)const{
 		if(x!=p.x)return x<p.x;
 		return y<p.y;
 	}
 };
 std::vector<P> nums;
 
 int main(){
 	int yToX[20010];
	for(int i=0;i<20010;i++)yToX[i]=-20000;
  	std::vector<P> points;
 	P p;
 	int n;
	scanf("%d",&n);
 	for(int i=0;i<n;i++){
 		scanf("%d %d",&p.x,&p.y);
 		p.y+=10000;
 		points.push_back(p);
 	}
 	std::sort(points.begin(),points.end());
 	int ans=20*10000*10000;
 	int len=sqrt(ans);
 	for(int i=0;i<n;i++){
 		p=points[i];
 		int top=len+p.y+2;
 		int down=p.y-2-len;
 		if(top>=20000)top=20000;
 		if(down<=0)down=0;
 		for(int i=top;i>=down;i--){
 			if(yToX[i]<-10000)continue;
 			int t=(p.y-i)*(p.y-i)+(p.x-yToX[i])*(p.x-yToX[i]);
 			if(ans>t){
 				ans=t;
 				len=sqrt(ans);
 			}
 		}
 		yToX[p.y]=p.x;
 	}
 	printf("%d\n",ans);
 }






*aoj0586　Palindrome
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0586
２ｎ桁か２ｎ+1桁で真中の桁の数字が指定された対称数を考える。
この時素数を作れるなら最大の対称数の素数を、作れないなら最も大きな対称数を返せという問題。

解法
全く分からなかったのであり得そうな範囲を全部手元のパソコンで計算して配列に埋め込みテーブル化しました。
この問題、答えを返す関数をf(n,c)としてfが高速に答えを計算して返す方法もあるようですが私は思いつかない状態です。
後日リベンジしたいですねこの問題は。


 #include<stdio.h>
 
 int main(){
 	char ans1[20][20][30]={	{"0","1","2","3","4","5","6","7","8","9"}
 				,{"101",	"919",	"929",	"131",	"999",	"757",	"999",	"373",	"787",	"797"}
 				,{"94049",	"93139",	"96269",	"98389",	"96469",	"97579",	"98689",	"96769",	"97879",	 "95959"}
 				,{"9980899",	"9981899",	"9932399",	"9923299",	"9754579",	"9965699",	"9926299",	"9957599",	"9978799",	"9989899"}
				,{"998202899",	"999212999",	"999727999",	"999434999",	"996949699",	"999454999",	"999565999",	"999676999",	"999686999",	 "998898899"}
 				,{"99986068999",	"99999199999",	"99976267999",	"99994349999",	"99983438999",	"99981518999",	"99988688999",	"99995759999",	 "99991819999",	"99998989999"}
 				,{"9999980899999",	"9999961699999",	"9999852589999",	"9999913199999",	"9999814189999",	"9999545459999",	 "9999886889999",	"9999987899999",	"9999938399999",	"9999919199999"}
 				,{"999993202399999",	"999998616899999",	"999999626999999",	"999999232999999",	"999999545999999",	"999999757999999",	 "999997464799999",	"999999272999999",	"999999787999999",	"999999292999999"}
 				,{"99999953035999999",	"99999959195999999",	"99999999299999999",	"99999971317999999",	"99999983438999999",	"99999981518999999",	  "99999964646999999",	"99999978787999999",	"99999997879999999",	"99999985958999999"}
  				,{"9999999890989999999",	"9999999931399999999",	"9999999992999999999",	"9999999883889999999",	"9999999864689999999",	"  9999999945499999999",	"9999999586859999999",	"9999999847489999999",	"9999999918199999999",	"9999999889889999999"}
 				};
 	char ans2[12][30]={"0","11","9999","999999","99999999","9999999999","999999999999","99999999999999","9999999999999999","999999999999999999","99999999999999999999"};
 	int n,c;
 	scanf("%d %d",&n,&c);
 	printf("%s\n",c<0?ans2[n]:ans1[n][c]);
 }








*aoj0588　Simple Calculator
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0588
優先順位のない式で四則演算を行う問題。

解法
手前から順番に読み込んで処理するだけです。

 #include<stdio.h>
 
 int main(){
 	int ans,a;
 	char t[3]=" ";
 	scanf("%d",&ans);
 	while(1){
 		scanf("%s",t);
 		if(t[0]=='=')break;
 		scanf("%d",&a);
 		if(t[0]=='+')ans+=a;
 		if(t[0]=='-')ans-=a;
 		if(t[0]=='*')ans*=a;
 		if(t[0]=='/')ans/=a;
 	}
 	printf("%d\n",ans);
 }




*aoj0589　Production
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0589
工場の生産記録から各製品の製造数を答える問題。


解法
std::stringをそのまま使うと辞書順になるので構造体でラップし直して後はstd::mapで集計して終わりです。

 #include<stdio.h>
 #include<string>
 #include<map>
 
 struct Goods{
 	std::string name;
 	bool operator<(const Goods& g)const{
 		if(name.size()!=g.name.size())return name.size()<g.name.size();
 		return name<g.name;
 	}
 };
 
 int main(){
 	int n,m;
	char name[10];
  	std::map<Goods,int> ans;
	Goods g;
  	scanf("%d",&n);
 	for(int i=0;i<n;i++){
 		scanf("%s %d",name,&m);
 		g.name=name;
 		if(ans.find(g)==ans.end())ans[g]=0;
 		ans[g]+=m;
 	}
 	for(std::map<Goods,int>::iterator it=ans.begin();it!=ans.end();it++){
 		printf("%s %d\n",(*it).first.name.c_str(),(*it).second);
 	}
 }



*aoj0590 Available Areas
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0590
与えられた自然数が、2xy+x+y x>0,y>0　ｘ、ｙは自然数として表現できるか判別する問題。

解法
yを決定すると面積をｓとして
a=(s-y)/(2y+1)が自然数になれば答えが存在します。
式の対称性から考えてa>=yの間だけ計算すれば十分なようです。

 #include<stdio.h>
 #include<iostream>
 int main(){
 	int n,ans=0;
  	scanf("%d",&n);
 	int y,s;
 	for(int i=0;i<n;i++){
 		scanf("%d",&s);
 		bool ok=false;
 		for(y=1;(2*y+1)<=s-y;y++){
 			if((s-y)%(2*y+1)==0){
 				ok=true;
  				break;
 			}
 			int t=(s-y)/(2*y+1);
 			if(t<y)break;
 		}
 		ans+=(ok==false);
 	}
 	printf("%d\n",ans);
 }