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

「AOJ11～20」(2011/08/21 (日) 17:43:56) の最新版変更点

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

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

*0011　Drawing Lots
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0011&lang=jp
あみだくじを表現するデータが与えられるので、何番目のくじから始めたら何番目にたどり着くかを全出力する問題です。
あみだくじの番号をつけた配列を用意し、これを上から読んで交換があればそれを入れ替えるだけで実装できます。




 #include<stdio.h>
 #include <algorithm>
 int main(){
	int d[32],w,h,i,l,R;
	scanf("%d %d",&w,&h);
	for(i=1;i<=w;i++){
		d[i]=i;
	}
	for(i=0;i<h;i++){
		scanf("%d,%d",&l,&R);
		std::swap(d[l],d[R]);
	}
	for(int i=1;i<=w;i++){
		printf("%d\n",d[i]);
	}
 }




----
*0012　A Point in a Triangle
三角形ＡＢＣと点Ｐの座標が与えられます。
点ｐが三角形の中にあればＹＥＳでないならＮＯと出力するという問題です。

ベクトルで解きます。
→AP=t(→AB)+s(→AC)。　→はベクトルを表します。
この式が0<=t<=1 && 0<=s<=1 && s+t<=1なら点ｐは三角形の中にあります。
この事実を使って高校数学の教科書通り素直に実装しましょう。


 #include<stdio.h>
 bool inDelta(double xs[3],double ys[3],double x,double y){
	double x1,x2,x3,y1,y2,y3,k,s,t,u;
	x1=xs[1]-xs[0];
	y1=ys[1]-ys[0];
	x2=xs[2]-xs[0];
	y2=ys[2]-ys[0];
	x3=x-xs[0];
	y3=y-ys[0];
	k=(x1*y2-x2*y1);
	if(k==0){
		return false;
	}
	s=(y2*x3-x2*y3)/k;
	t=(x1*y3-y1*x3)/k;
	u=s+t;
	
	if(s<=0.0 || 1.0<=s || t<=0.0 || 1.0<=t || u<=0.0 || 1.0<=u){
		return false;
	}else{
		return true;
	}
 }
 int main(){
	double xs[3],ys[3],x,y;
	while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2],&x,&y)!=EOF){
		if(inDelta(xs,ys,x,y)==true){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
 }









----
*0013　Switching Railroad Cars
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0013&lang=jp
電車車両入替え用の線路に出入りする電車のデータが与えれます。
データより電車の出た順番を出力してください。
入れ替え路線はスタックと同じ構造になっているのでスタックをそのまま使うだけの問題です。



 #include<stdio.h>
 #include<stack>
 int main(){
	std::stack<int> s;
	int l;
	while(scanf("%d",&l)!=EOF){
		if(l==0){
			printf("%d\n",s.top());
			s.pop();
		}else{
			s.push(l);
		}
	}
 }




----
*0014 Integral
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0014&lang=jp
近似法でy=x^2 (0<=x<=600) y=0　x=600で囲まれる部分の面積を出力してください。
高校数学で習う方法をそのまま使うだけです。


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







----
*0015　National Budget
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015&lang=jp

80桁以内の2数a,bが与えられます。
2数の和が80ケタいないならその和を、80桁以上ならＮＡと出力する問題です。
a,bともに一桁ずつ右づめで文字列として数値を確保し、a+bを下の桁から小学校で習った筆算と同じ手法で計算してa+bを計算します。



 #include<string.h>
 #include <iostream> 
 #include <algorithm>
 void re(std::string& s){
	int l=s.size(),m=l/2;
	for(int i=0;i<m;i++){
		std::swap(s[l-i-1],s[i]);
	}
 }
 int main(){
	std::string s1,s2,s3;
	int n,m,u,s;
	char l,t;
	std::cin>>n;
	for(int i=0;i<n;i++){
		std::cin>>s1>>s2;
		s3="";
		m=s1.size()>s2.size()?s1.size():s2.size();
		if(m>80){
			std::cout<<"overflow\n";
			continue;
		}
		re(s1);
		re(s2);
		s1.append(m-s1.size(),'0');
		s2.append(m-s2.size(),'0');
		l=0;
		for(int i=0;i<m;i++){
			s=(s1[i]-'0')+(s2[i]-'0')+l;
			l=s/10;
			t=s%10;
			s3.append(1,(char)(t+'0'));
		}
		if(l!=0) s3.append(1,(char)(l+'0'));
		if(s3.size()>80){
			std::cout<<"overflow\n";
			continue;
		}
		re(s3);
		std::cout<<s3<<"\n";
	}
 }








----
*0016　Treasure Hunt
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0016&lang=jp
愚直に実装するだけ。
何か賢い方法があるとも思えない。


 #include<stdio.h>
 #include<math.h>
 int main(){
	int r,n,nowR=90;
	double x=0,y=0,tr;
	scanf("%d,%d",&n,&r);
	while(r!=0 || n!=0){
		tr=nowR/180.0*M_PI;
		x+=n*cos(tr);
		y+=n*sin(tr);
		nowR=(nowR-r+360)%360;
		scanf("%d,%d",&n,&r);
	}
	printf("%d\n%d\n",(int)x,(int)y);
 }







----
*0017　Caesar Cipher
the this thatのほうをずらした方が早いのは分かっているが計算量が小さいので意味なし。
楽な実装を選択。

 #include<stdio.h>
 #include<string>
 int main(){
	char c[81];
	std::string t;
	while(scanf("%[^\n]%*c",c)!=EOF){
		t=c;
		for(int i=0;i<27;i++){
			for(int j=0;j<t.size();j++){
				if('a'<=t[j] && t[j]<='z'){
					t[j]=(t[j]-'a'+1)%26+'a';
				}
			}
			if(t.find("the")!=-1 || t.find("this")!=-1 || t.find("that")!=-1){
				printf("%s\n",t.c_str());
				break;
			}
		}
	}
 }








----
*0018　Sorting Five Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0018&lang=jp
実装するだけ。
一文字縮めるのにはこだわらないので適当。

 #include<stdio.h>
 #include <algorithm>

 int main(){
	int a[5];
	for(int i=0;i<5;i++){
		scanf("%d",&a[i]);
	}
	std::sort(a,a+5);
	printf("%d %d %d %d %d\n",a[4],a[3],a[2],a[1],a[0]);
 }






----
*0019 Factorial
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0019&lang=jp
long long int万歳な問題。
これがなかったらこの問題はビックインテガーが必要になるので少し難しい問題になる。

 #include <stdio.h>
 int main(){
    long long int t=1;
    int n,i;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        t*=i;
    }
    printf("%llu\n",t);
 }









----
*0020　Capitalize
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0020&lang=jp
順番に読んで処理するだけのパイプ処理。


 #include <stdio.h>
 int main()
 {
	int n;
	while(~(n = getchar()))
		putchar(96<n&&n<123?n-32:n);
	return 0;
 }

*0011　Drawing Lots
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0011&lang=jp
あみだくじを表現するデータが与えられるので、何番目のくじから始めたら何番目にたどり着くかを全て出力する問題です。
あみだくじの上端の紐を表す番号をつけた配列を用意し、これを上から読んで交換があればそれを入れ替えるだけで実装できます。




 #include<stdio.h>
 #include <algorithm>
 int main(){
	int d[32],w,h,i,l,R;
	scanf("%d %d",&w,&h);
	for(i=1;i<=w;i++){
		d[i]=i;
	}
	for(i=0;i<h;i++){
		scanf("%d,%d",&l,&R);
		std::swap(d[l],d[R]);
	}
	for(int i=1;i<=w;i++){
		printf("%d\n",d[i]);
	}
 }




----
*0012　A Point in a Triangle
三角形ＡＢＣと点Ｐの座標が与えられます。
点ｐが三角形の中にあればＹＥＳでないならＮＯと出力するという問題です。

ベクトルで解きます。
→AP=t(→AB)+s(→AC)。　→はベクトルを表します。
この式が0<=t<=1 && 0<=s<=1 && s+t<=1なら点ｐは三角形の中にあります。
この事実を使って高校数学の教科書通り素直に実装しましょう。


 #include<stdio.h>
 bool inDelta(double xs[3],double ys[3],double x,double y){
	double x1,x2,x3,y1,y2,y3,k,s,t,u;
	x1=xs[1]-xs[0];
	y1=ys[1]-ys[0];
	x2=xs[2]-xs[0];
	y2=ys[2]-ys[0];
	x3=x-xs[0];
	y3=y-ys[0];
	k=(x1*y2-x2*y1);
	if(k==0){
		return false;
	}
	s=(y2*x3-x2*y3)/k;
	t=(x1*y3-y1*x3)/k;
	u=s+t;
	
	if(s<=0.0 || 1.0<=s || t<=0.0 || 1.0<=t || u<=0.0 || 1.0<=u){
		return false;
	}else{
		return true;
	}
 }
 int main(){
	double xs[3],ys[3],x,y;
	while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2],&x,&y)!=EOF){
		if(inDelta(xs,ys,x,y)==true){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
 }









----
*0013　Switching Railroad Cars
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0013&lang=jp
電車車両入替え用の線路に出入りする電車のデータが与えれます。
データより電車の出た順番を出力してください。
入れ替え路線はスタックと同じ構造になっているのでスタックをそのまま使うだけの問題です。



 #include<stdio.h>
 #include<stack>
 int main(){
	std::stack<int> s;
	int l;
	while(scanf("%d",&l)!=EOF){
		if(l==0){
			printf("%d\n",s.top());
			s.pop();
		}else{
			s.push(l);
		}
	}
 }




----
*0014 Integral
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0014&lang=jp
近似法でy=x^2 (0<=x<=600) y=0　x=600で囲まれる部分の面積を出力してください。
高校数学で習う方法をそのまま使うだけです。


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







----
*0015　National Budget
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015&lang=jp

80桁以内の2数a,bが与えられます。
2数の和が80ケタいないならその和を、80桁以上ならＮＡと出力する問題です。
a,bともに一桁ずつ右づめで文字列として数値を確保し、a+bを下の桁から小学校で習った筆算と同じ手法で計算してa+bを計算します。



 #include<string.h>
 #include <iostream> 
 #include <algorithm>
 void re(std::string& s){
	int l=s.size(),m=l/2;
	for(int i=0;i<m;i++){
		std::swap(s[l-i-1],s[i]);
	}
 }
 int main(){
	std::string s1,s2,s3;
	int n,m,u,s;
	char l,t;
	std::cin>>n;
	for(int i=0;i<n;i++){
		std::cin>>s1>>s2;
		s3="";
		m=s1.size()>s2.size()?s1.size():s2.size();
		if(m>80){
			std::cout<<"overflow\n";
			continue;
		}
		re(s1);
		re(s2);
		s1.append(m-s1.size(),'0');
		s2.append(m-s2.size(),'0');
		l=0;
		for(int i=0;i<m;i++){
			s=(s1[i]-'0')+(s2[i]-'0')+l;
			l=s/10;
			t=s%10;
			s3.append(1,(char)(t+'0'));
		}
		if(l!=0) s3.append(1,(char)(l+'0'));
		if(s3.size()>80){
			std::cout<<"overflow\n";
			continue;
		}
		re(s3);
		std::cout<<s3<<"\n";
	}
 }








----
*0016　Treasure Hunt
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0016&lang=jp
一定のルールの上で座標平面上を移動しつづけた時、最後にいる座標を出力する問題です。
回転して進むということを繰り返すのでそれをそのままワンステップの移動を一つ一つ実装します。


 #include<stdio.h>
 #include<math.h>
 int main(){
	int r,n,nowR=90;
	double x=0,y=0,tr;
	scanf("%d,%d",&n,&r);
	while(r!=0 || n!=0){
		tr=nowR/180.0*M_PI;
		x+=n*cos(tr);
		y+=n*sin(tr);
		nowR=(nowR-r+360)%360;
		scanf("%d,%d",&n,&r);
	}
	printf("%d\n%d\n",(int)x,(int)y);
 }







----
*0017　Caesar Cipher
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0017&lang=jp
シーザー暗号で暗号化された文章を複合する問題です。
正しい複合ができた時Ｔｈｅ　Ｔｈｉs　Ｔｈａｔ　が含まれているのでそれをヒントに複合します。
文字コードがa～zまで連番で並んでいるということを利用して解きます。
問題文に解き方が書かれているのでそのまま実装しましょう。
今回のコードでは一つずつ文字をずらして解きました。



 #include<stdio.h>
 #include<string>
 int main(){
	char c[81];
	std::string t;
	while(scanf("%[^\n]%*c",c)!=EOF){
		t=c;
		for(int i=0;i<27;i++){
			for(int j=0;j<t.size();j++){
				if('a'<=t[j] && t[j]<='z'){
					t[j]=(t[j]-'a'+1)%26+'a';
				}
			}
			if(t.find("the")!=-1 || t.find("this")!=-1 || t.find("that")!=-1){
				printf("%s\n",t.c_str());
				break;
			}
		}
	}
 }








----
*0018　Sorting Five Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0018&lang=jp
5つの整数が与えられるので大きい順に出力してください。
sort機能を理解しているかどうかだけが問われる問題なのですぐに解けると思います。


 #include<stdio.h>
 #include <algorithm>

 int main(){
	int a[5];
	for(int i=0;i<5;i++){
		scanf("%d",&a[i]);
	}
	std::sort(a,a+5);
	printf("%d %d %d %d %d\n",a[4],a[3],a[2],a[1],a[0]);
 }






----
*0019 Factorial
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0019&lang=jp
ｎ！を出力せよという問題。
問題ではｎ！20まであるのでintを使うと数値があふれてしまいます。
巨大な数を扱えるlong long intという型を使って求めます。


 #include <stdio.h>
 int main(){
    long long int t=1;
    int n,i;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        t*=i;
    }
    printf("%llu\n",t);
 }









----
*0020　Capitalize
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0020&lang=jp
文字を読み込んで、半角英小文字を半角英大文字に変換する問題です。
アルファベットどのエンコードでも同じ番号が与えられているのでそれを利用して解きます。
一文字ずつ読み、文字が半角英小文字なら大文字に変換して出力、でないならそのまま出力します。


 #include <stdio.h>
 int main()
 {
	int n;
	while(~(n = getchar()))
		putchar(96<n&&n<123?n-32:n);
	return 0;
 }