AOJ11～20 - c21coterie @ ウィキ

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;
}