2.3 AOJ-0006 to 0010

今日もAOJの問題を解いていた。

0006

文字列の反転問題。

0007

毎週5%の利子がついて、しかも1000円未満は切り上げられるという闇金業者の借金が、n週間後にはいくらになるか、という教育上よろしいのか疑われる問題。
1000円未満の切り上げ処理がポイント。むしろそこしかポイントが無い。

//一の位から数えてketa桁未満で繰り上げる
void keta_up(int &num, int keta){
	int p = pow(10, keta);
	int n = num / p;
	if(num-n*p > 0){
		num /= p;
		num += 1;
		num *= p;
	}
}

0008

0~9なる整数a,b,c,dで、a+b+c+d=nなる組み合わせは何通りか、という問題。
探索系の問題だけど、この場合はコレで解ける。

#include <iostream>

using namespace std;

int main(){
	int n;
	while(cin >> n){
		int ans_num = 0;
		for(int a=0; a<10; ++a){
			for(int b=0; b<10; ++b){
				for(int c=0; c<10; ++c){
					for(int d=0; d<10; ++d){
						if(a+b+c+d == n)	++ans_num;
					}
				}
			}
		}
		cout << ans_num << endl;
	}
	
	return 0;
}

こんな問題もあったねぇ。

0009

n以下の素数はいくつあるか、という問題。範囲が決められているのでエラトステネスの篩を使う。これ以外の選択肢は無い。篩のために使う変数は、グローバルにしておくこと(スタック領域じゃオーバーフローを起こす)。

#include <iostream>
#include <vector>

using namespace std;

const int MAX_NUM = 1000000;

bool prime_flag[MAX_NUM];
vector<int> prime;

void check_prime(){
	prime_flag[0] = false;
	for(int i=1; i<MAX_NUM; ++i){
		if(prime_flag[i] == true){
			int num = i+1;
			for(int j=2*num; j<MAX_NUM+1; j+=num){
				prime_flag[j-1] = false;
			}
			prime.push_back(i+1);
		}
	}
}

int main(){
	for(int i=0; i<MAX_NUM; ++i)	prime_flag[i] = true;
	check_prime();
	int n;
	while(cin >> n){
		int i;
		for(i=0; i<(int)prime.size(); ++i){
			if(prime[i] > n)	break;
		}
		cout << i << endl;
	}
	
	return 0;
}

0010

三点が与えられるので、それで作られる三角形の外接円の中心座標と半径を求めよ、とのこと。
中心座標の導出がめっちゃめんどい。2弦の垂直二等分線の交点がそれなので、それを導出してみる。
まず、(x1,y1)と(x2,y2)の垂直二等分線は以下のような直線である。

この時点で割と吐き気がする。
よって、

この連立方程式を解けば良い。ゲェ～ッ。
行列使って解いて、解は以下のようになる。

これはひどい。
一応、ちゃんと正解は出せる。動作も非常に高速である。見た目はともかく。
半径の導出は簡単なので省略。