AOJ1～10 - c21coterie @ ウィキ

---

0001 List of Top 3 Hills

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0001&lang=jp
山の高さをあらわす整数が10個与えられるので、その中から上位３つの山の高さを表示せよ。
基本機能であるソートを理解しているかどうかが問われる問題です。
基本機能を理解しているならそのまま実装しましょう。

#include<stdio.h>
#include <algorithm>
int main(){
int m[10],i;
for(i=0;i<10;i++){scanf("%d",&m[i]);}
std::sort(m,m+10);
for(int i=9;i>6;i--)printf("%d\n",m[i]);
}

---

0002 Digit Number

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0002&lang=jp
2つの整数の和の桁数を表示する問題。
基本機能である読み込み関数の使い方やmod演算等を理解しているか問われる問題です。
そのまま実装するだけです。

#include<stdio.h>
int main(){
int a,b,c,d=0;
while(scanf("%d %d",&a,&b)!=EOF){
	c=a+b;
	d=0;
	while(c/10!=0){
		c/=10;
		d++;
	}
	printf("%d\n",d+1);
}
}

---

0003 Is it a Right Triangle?

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0003&lang=jp
三角形の3辺が与えられるので、それが直角三角形であるならＹｅｓでないならＮｏと答える問題。
3平方の定理と基本的な計算式を記述する能力が問われます。

#include<stdio.h>
int main(){
int a,b,c,d;
scanf("%d",&d);
for(int i=0;i<d;i++){
	scanf("%d %d %d",&a,&b,&c);
	a*=a;
	b*=b;
	c*=c;
	if(a==b+c || b==c+a || c==b+a){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
}
}

---

0004　Simultaneous Equation

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0004&lang=jp
ax+by=c
dx+ey=f
という定義式があります。
a,b,c,d,e,fの値が与えられるので、ｘ、ｙを求めてください。

2*2の逆行列を理解しているかが問われる問題です。
高校数学の教科書通りに実装します。

#include<stdio.h>
int main(){
double a,b,c,d,e,f,x,y,k;
while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)!=EOF){
	k=a*e-b*d;
	x=(e*c-b*f)/k+0.0;
	y=(-d*c+a*f)/k+0.0;
	printf("%.3lf %.3lf\n",x,y);
}
}

---

0005　GCD and LCM

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp
2数a,bが与えられるのでaとｂの最小公倍数と最大公約数を求める問題です。
初歩のアルゴリズムの教科書に載っている通りの手順で求めるだけです。
gcdが最大公約数、a*(b/q)が最大公約数となります。

#include<stdio.h>
int gcd(int a, int b)
{
   int c;
   while (b > 0)
   {
       c = a % b;
       a = b;
       b = c;
   }
   return a;
}
int main(){
int a,b,q;
while(scanf("%d %d",&a,&b)!=EOF){
	q=gcd(a,b);
	printf("%d %d\n",q,a*(b/q));
}
}

---

0006 Reverse Sequence

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0006&lang=jp
文字列が一行ずつ入力されるので、文字列を一行ずつ逆から表示します。
stdのrevers命令を使えば一行で済みますが、文字列を配列的に扱ってみました。

#include<stdio.h>
#include<string.h>
int main(){
char t[21];
scanf("%s",t);
for(int i=strlen(t)-1;i>=0;i--){
	printf("%c",t[i]);
}
printf("\n");
}

---

0007 Debt Hell

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0007&lang=jp
借金の利息計算です。
利息日ごとに1.05倍して1000円以下は切り上げする処理を書くだけです。

#include<stdio.h>
int main(){
int d=100000,n;
scanf("%d",&n);
for(int i=0;i<n;i++){
	d*=1.05;
	d+=d%1000==0?0:1000-d%1000;
}
printf("%d\n",d);
}

---

0008 Sum of 4 Integers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008&lang=jp
50 以下の正の整数 n を入力し、0 ～ 9 の範囲の整数 a, b, c, d の組で
a + b + c + d = n
を満たすものの組み合わせ数を出力するプログラムを作成して下さい。
普通にループを回すだけでも解けますがナップザック法を応用してみました。

#include<stdio.h>
#include<string.h>
int main(){
unsigned int m[5][52],p,q;
memset(m,0,1040);
m[0][0]=1;
for(int k=0;k<51;k++){
	for(int i=0;i<40;i++){
		p=i/10;
		q=i%10;
		if(k+p>50) continue;
		m[p+1][k+q]+=m[p][k];
	}
}
while(scanf("%d",&p)!=EOF){
	printf("%d\n",m[4][p]);
}
}

---

0009　Prime Number

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp
自然数ｎが与えられるのでｎ以下の素数が何個あるかを答える問題です。
下から上に数え上げてそれをメモするだけです。
このコード、数え上げに使った配列をそのまま使えばよくＭａｐに入れたのは蛇足なコードでした。

#include<stdio.h>
#include<string.h>
#include<map>
std::map<int,int> s;
int p;
void setSo(){
const m=1000003;
bool t[m];
p=1;
memset(t,m,true);
s[2]=p;
for(int i=3;i<m;i+=2){
	if(t[m]==false) continue;
	p++;
	s[i]=p;
	for(int j=i*3;j<m;j+=i*2){
		t[j]=false;
	}
}
}
int main(){
setSo();
int d;
std::map<int,int>::iterator it;
while(scanf("%d",&d)!=EOF){
	it=s.lower_bound(d);
	it=it!=s.begin()?it--:it;
	printf("%d\n",(*it).second);
}
}

---

0010　Circumscribed Circle of a Triangle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010&lang=jp
三角形の頂点座標が与えられるので外心の座標を出力する問題です。
私の場合重心座標で求めまたしたが、求め方は多数ある問題だと思います。

#include<stdio.h>
#include<math.h>
double getDoubleSin(double x1,double y1,double x2,double y2){
double len1,len2,s,c;
len1=sqrt(x1*x1+y1*y1);
len2=sqrt(x2*x2+y2*y2);
s=fabs(x1*y2-y1*x2)/(len1*len2);
c=(x1*x2+y1*y2)/(len1*len2);
//printf("(%lf %lf)",s,c);
return 2*s*c;
}
double getR(double a,double b,double c){
double ans=a*b*c;
ans/=sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c));
return ans;
}
int main(){
double xs[3],ys[3];
double g1,g2,g3;
double vx1,vy1,vx2,vy2;
double g[3];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
	scanf("%lf %lf %lf %lf %lf %lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2]);
	double ansX=0,ansY=0,gSum=0;
	double lens[3];
	for(int i=0;i<3;i++){
		vx1=xs[(i+1)%3]-xs[i];
		vy1=ys[(i+1)%3]-ys[i];
		vx2=xs[(i+2)%3]-xs[i];
		vy2=ys[(i+2)%3]-ys[i];
		lens[i]=sqrt(vx1*vx1+vy1*vy1);
		g[i]=getDoubleSin(vx1,vy1,vx2,vy2);
		//printf("(2s=%lf)\n",g[i]);
		ansX+=g[i]*xs[i];
		ansY+=g[i]*ys[i];
		gSum+=g[i];
	}
	double R=getR(lens[0],lens[1],lens[2]);
	ansX/=gSum;
	ansY/=gSum;
	printf("%.3lf %.3lf %.3lf\n",ansX,ansY,R);
}
}