kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Videotape(AOJ No.0074), BMI(AOJ No.0075), Treasure Hunt II(AOJ No.0076), Run Length(AOJ No.0077), Magic Square(AOJ No.0078), Area of Polygon(AOJ No.0079), Third Root(AOJ No.0080)

Online Judge

リポジトリ

Videotape(AOJ No.0074)

標準録画で 120 分のビデオテープがある。テープを完全に巻き戻した状態でビデオデッキのカウンタを 00:00:00 にし、標準録画モードで録画したときのカウンタ値（時、分、秒)が与えられ、残り録画可能時間と、3倍録画モードで録画した倍の残り録画可能時間を求める。

コード

import java.util.*;
public class aoj0074 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			int h = stdin.nextInt(), m = stdin.nextInt(), s = stdin.nextInt();
			if(h == -1 && m == -1 && s == -1) break;
			int diff = 7200 - (h*3600 + m*60 + s), temp = diff;
			h = temp/3600; temp %= 3600; m = temp/60; s = temp % 60;
			System.out.printf("%02d:%02d:%02d\n", h,m,s);
			temp = diff*3;
			h = temp/3600; temp %= 3600; m = temp/60; s = temp % 60;
			System.out.printf("%02d:%02d:%02d\n", h,m,s);
		}
	}
}

BMI(AOJ No.0075)

学籍番号、体重、身長の一覧が与えられて、BMI(Body Mass Index)が25以上の学籍番号を求める。
BMI=\frac{weight[kg]}{(height[m])^2}

コード

まただよ。入力の体重、身長の単位も出力順も問題文に明記してないよ。

import java.util.*;
public class aoj0075 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			String[] line = stdin.nextLine().split(",");
			if(Double.parseDouble(line[1])/Math.pow(Double.parseDouble(line[2]), 2) >= 25)
				System.out.println(line[0]);
		}
	}
}

Treasure Hunt II(AOJ No.0076)

1.まず、町外れの井戸から、真東に 1m の地点に立ち、まっすぐ井戸の方向を向け。
2.右回りに 90 度向きを変え、1m直進したら、まっすぐ井戸の方向を向け。
3.右回りに 90 度向きを変え、1m直進したら、まっすぐ井戸の方向を向け。
\vdots
ステップnまで、繰り返したときの座標を答える(井戸から東にx[m],北にy[m])

アルゴリズム

現在の位置を \vec{p}=[ x, y ]^Tとする。
回転移動の一次変換は、
\left[ \begin{array}{c}x'\\y'\end{array} \right] = \left[ \begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right] \left[ \begin{array}{c}x\\y\end{array}\right] = \left[ \begin{array}{c} x\cos \theta - y \sin \theta \\ x \sin \theta + y\cos \theta \end{array}\right]
\theta=\frac{\Pi}{2}とすれば、 [x', y']^T = [-y, x]^T
なので、 \vec{p}を正規化し、上の一次変換を行い \vec{p}に加えれば、
右回りに 90 度向きを変え、1m直進したら、まっすぐ井戸の方向を向くことになる。
よって一次変換(回転)でベクトルの大きさが変化しないことに注意すれば、 \vec{p_{i+1}} = \vec{p_i}+\frac{1}{|\vec{p_i}|}\left[ \begin{array}{c}-y \\ x\end{array}\right] で更新すれば良いことがわかる。

コード

import java.util.*;
public class aoj0076 {
	static final Scanner stdin = new Scanner(System.in);
	static final double RIGHT = Math.PI/2.0;
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != -1){
			double x = 1.0, y = 0.0;
			for(int i = 0; i < n-1; ++i){
				double coef = 1/Math.hypot(x, y), temp = x;
				x -= coef*y;
				y += coef*temp;
			}
			System.out.printf("%f\n%f\n",x,y);
		}
	}
}

Run Length(AOJ No.0077)

ランレングス符号化された英数字文を復号する。
@の後に、レングス(1文字), 連ねる文字(1文字)が並ぶ。

コード

import java.util.*;
import java.util.*;
public class aoj0077 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			char[] line = stdin.nextLine().toCharArray();
			for(int i = 0; i < line.length; ++i){
				if(line[i]=='@'){
					int n = line[i+1]-'0';
					while(n-->0) System.out.print(line[i+2]);
					i+=2;
				}else{
					System.out.print(line[i]);
				}
			}
			System.out.println("");
		}
	}
}

Magic Square(AOJ No.0078)

次の手順に従って、 n\times nの魔方陣を求める。

  1. 中央のマス目のちょうど一つ下のマス目に１をいれる。
  2. 次の数字を右斜め下のマス目にいれる。ただし、数字をいれようとしたマス目が正方形からはみ出している場合、すでに数字が埋まっている場合は以下の方法に従って数字を入れるマス目を探す。
    1. 右にはみ出した場合には、同じ行の左はしに、左にはみ出した場合には、同じ行の右はしに、下にはみ出した場合には、同じ列の一番上に数字をいれる。
    2. 数字をいれようとしたマス目が埋まっているときには、その埋まっているマス目の左斜め下のマス目にいれる。
  3. 全てのマス目が埋まるまで２を繰り返す。

制約
3\leq n \leq 15
nは奇数

奇数でない時の作り方も調べたので、リンクを貼っておく(魔方陣 - Wikipedia, http://www2u.biglobe.ne.jp/~zed/m_stitle.htm)
Matlabのmagic関数の説明では、
次数が奇数の場合と、4の倍数の場合、4の倍数でない偶数の場合で異なるアルゴリズムで計算しているようなので、
今度作ってみたい(Octaveで検証できると思う)。

コード

import java.util.*;
public class aoj0078 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt();
			if(n == 0) break;
			int k = 0;
			int[][] a = new int[n][n];
			for(int i = -n/2; i <= n/2; ++i)
				for(int j = 0; j < n; ++j)
					a[(j+i+n)%n][(j-i+n)%n] = ++k;
			for(int i = 0; i < n; ++i)
				for(int j = 0; j < n; ++j)
					System.out.printf("%4d%s", a[i][j], (j == n-1 ? "\n" : "") );
		}
	}
}

Area of Polygon(AOJ No.0079)

凸多角形の頂点( p_1, p_2, \cdots , p_n )の座標が与えられて、凸多角形の面積を求める。
ヘロンの公式 s=\frac{a+b+c}{2}, S=\sqrt{s(s-a)(s-b)(s-c)}を使ってもよい。
制約
3\leq n \leq 20

アルゴリズム1

適当な多角形の内点qを求め、△ p_i p_{i+1}qの面積の和を求める。
凸多角形なので、適当に3点取って、その重心求めれば、内点になっている。
面積はヘロンの公式を使うより、公式 \frac{1}{2}|cross(\vec{a},\vec{b})| = \frac{1}{2}||\vec{a}||\vec{n}|\sin \theta|を使った方がルートの計算が無いので正確。

アルゴリズム2

多角形の公式
\frac{1}{2}|\sum_{i=1}^n (x_i - x_{i+1})(y_i + y_{i+1})|を使う方がよりシンプル。
※ x_{n+1} = x_1, y_{n+1} = y_1

コード

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0079 {
	static final Scanner stdin = new Scanner(System.in);
	static Solver solver = Solver.Square;
	public static void main(String[] args) { 
		ArrayList<Point> polygon = new ArrayList<Point>(); 
		while(stdin.hasNext()){
			String[] p = stdin.nextLine().split(",");
			polygon.add(new Point(Double.parseDouble(p[0]), Double.parseDouble(p[1])));
		}
		System.out.println(solver.solve((Point[])polygon.toArray(new Point[polygon.size()])));
	}
	static enum Solver {
		Square { @Override double solve(Point[] polygon) {
			Point p = (polygon[0].add(polygon[1]).add(polygon[2])).div(3.0);
			int n = polygon.length;
			double ret = 0.0;
			for(int i = 0; i < n; ++i)
				ret += Math.abs(polygon[i].sub(p).cross(polygon[(i+1)%n].sub(p)))/2.0;
			return ret;
		}}, Cross { @Override double solve(Point[] polygon) {
			return square(polygon);
		}};
		double solve(Point[] polygon){ return 0.0; }
	}
	@SuppressWarnings("serial") public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,y); }
		public Point(Point p){ super(p.x, p.y); }
		public final Point add(Point p){ return new Point( x + p.x, y + p.y ); }
		public final Point sub(Point p){ return new Point( x - p.x, y - p.y ); }
		public final Point div(double k){ return new Point( x/k, y/k ); }
		public final double cross(Point p){ return x * p.y - y * p.x; }
	}
	public static double square(Point[] polygon){
		int n = polygon.length;
		double res = 0.0;
		for(int i = 0; i < n; ++i){
			Point cur = polygon[i], next = polygon[(i+1)%n];
			res += (cur.x + next.x)*(cur.y - next.y);
		}
		return Math.abs(res/2.0);
	}
}

Third Root(AOJ No.0080)

qの三乗根をニュートン法で求める。
終了条件は解 xが |x^3 - q| < 0.00001qになった時.

コード

またかよ (#^ω^). 小数点6位まで出すって書いとけよ。

import java.util.*;

public class aoj0080 {
	static final Scanner stdin = new Scanner(System.in);
	static int q;
	public static void main(String[] args) throws Exception {
		while(stdin.hasNext()){
			q = stdin.nextInt();
			if(q == -1) break;
			System.out.printf("%.6f\n", Newton(q/2.0, Integer.MAX_VALUE, new Function(){
				@Override public double f(double x) { return x*x*x - q; }
				@Override public double fp(double x) { return 3*x*x; }
			}));
		}
	}
	public static boolean equal(double a, double b){ return Math.abs(a-b) < 1e-5*q; }	// a == b
	static interface Function {
		public double f(double x);
		public double fp(double x);
	}
	static double Newton(double x0, int N_MAX, Function func) throws Exception{
		double x = x0;
		for(int i = 0; i < N_MAX; ++i){
			double delta = func.f(x)/func.fp(x);
			x -= delta;
			if(equal(func.f(x), 0)) return x; //if(equal(delta, 0)) return x;
		}
		throw new Exception();
	}
}