「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
三角形ABCと点Pの座標が与えられます。
点pが三角形の中にあればYESでないならNOと出力するという問題です。

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


 #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桁以上ならNAと出力する問題です。
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
シーザー暗号で暗号化された文章を複合する問題です。
正しい複合ができた時The This That が含まれているのでそれをヒントに複合します。
文字コードが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
n!を出力せよという問題。
問題ではn!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;
 }