Differential II(AOJ No.0051), Factorial II(AOJ No.0052), Sum of Prime Numbers(AOJ No.0053), Sum of Nth decimal places(AOJ No.0054), Sequence(AOJ No.0055), Goldbach's Conjecture(AOJ No.0056), The Number of Area(AOJ No.0057), Orthogonal(AOJ No. 0058), Inter

Differential II(AOJ No.0051)

8個の数字(0〜9)が与えられて、並び替えてできた数字の最大値と最小値の差を求める。
並び替えたとき0から始まってもよい。

コード

char[]にして、ソート→StringBuilder(reverse)→parseIntで最小値と最大値を求めた

import java.util.*;
public class aoj0051 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n = stdin.nextInt(); stdin.nextLine();	
		while(n-->0){
			char[] input = stdin.nextLine().toCharArray();
			Arrays.sort(input);
			StringBuilder sb = new StringBuilder(new String(input));
			System.out.println(-Integer.parseInt(sb.toString()) + Integer.parseInt(sb.reverse().toString()));
		}
	}
}

Factorial II(AOJ No. 0052)

整数nが与えられて、n!の末尾の0の数を求める
制約
$n \leq 2000000000$

n！を素因数分解して、2*5のペアが何個あるかで、末尾の0の数が分る.
例えば、
$10! = 10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1$
この中で、2で割り切れるのは、 $10=2\times 5, 8 = 2 \times 4, 6 = 2\times 3, 4 = 2\times 2, 2 = 2\times 1$ の $\lfloor 10/2 \rfloor= 5$ 個
残っている5,4,3,2,1のうち2で割り切れるのは $4=2\times 2, 2 = 2\times 1$ の $\lfloor 5/2 \rfloor = 2$ 個
同様に、残っている2, 1の中で割り切れるのは2の $\lfloor 2/1 \rfloor = 1$ 個
残っている1は割り切れないので $\lfloor 1/2 \rfloor = 0$ 個
よって、10!の素因数分解の中に2は5+2+1 = 8個ある
同様にして、素因数分解の中に5が何個あるかが求まる。
ここで、n!を素因数分解したとき、必ず5の数より、2の数の方が多いので、結局n!の素因数分解の中の5の個数が、
n!の末尾の0の数になる。

コード

import java.util.*;
public class aoj0052 {
	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 res = 0;
			while((n/=5) != 0) res += n;
			System.out.println(res);
		}
	}
}

Sum of Prime Numbers(AOJ No.0053)

$p(i)$ を $i$ 番目の素数とする。
$n$ が与えられたときの、 $\sum_{i=1}^n p(i)$ を求める
制約
$0 < n \leq 10000$

コード

エラトステネスの篩で、累積和のテーブルを作るだけ

import java.util.*;
public class aoj0053 {
	static final Scanner stdin = new Scanner(System.in);
	static final int MAX = 1000000;
	static boolean[] sieve(int n){
		boolean[] ret = new boolean[n+1];
		Arrays.fill(ret, true);
		ret[0] = ret[1] = false;
		for(int i = 2; i*i <= n; ++i)
			if(ret[i]) for(int j = i*i; j < n; j+=i) ret[j] = false;
		return ret;
	}
	public static void main(String[] args) {
		boolean[] table = sieve(MAX);
		Stack<Integer> LUT = new Stack<Integer>();
		LUT.push(0);
		for(int i = 0; i <= MAX; ++i) if(table[i]) LUT.push(LUT.peek()+i);
		while(true){
			int n = stdin.nextInt();
			if(n==0) break;
			System.out.println(LUT.get(n));
		}
	}
}

Sum of Nth decimal places(AOJ No.0054)

整数a, b, nが与えられる。
f(i)をa/bの小数第i位としたときの、 $\sum_{i=1}^n f(i)$ を求める。

アルゴリズム

筆算するときみたいに
a *= 10;、
ans += $\lfloor a/b \rfloor$ ;
a %= b;
を繰り返す。

コード

doubleの乗除算を繰り返してやって、誤差で死んでしまった...orz
doubleの精度とnの最大値が分らないから確実にAcceptされる保証はないが、
String.format("%.10000f,...)で小数点の位置pを求めて、substring(p+1, p+1+n)を取り出して、答えを求めてもAcceptされたwww(solve2)。

import java.util.*;
public class aoj0054 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext())
			System.out.println(solve(stdin.nextInt(), stdin.nextInt(), stdin.nextInt()));
	}
	static int solve(int a, int b, int n){
		int res = 0;
		a %= b;
		for(int i=0; i<n; ++i){
			a *= 10;
			res += a/b;
			a %= b;
		}
		return res;
	}
	static int solve2(int a, int b, int n){
		int res = 0;
		String s = String.format("%.1000f", (double)a/b);
		int p = s.indexOf('.');
		char[] c = s.substring(p+1,p+1+n).toCharArray();
		for(char i: c) res += (i-'0');
		return res;
	}
}

Sequence(AOJ No.0055)

数列が次のように定義されている。
$a_{2n} = 2a_{2n-1}$ $(n = 1, 2, 3, \cdots )$
$a_{2n+1} = \frac{a_{2n}}{3}$ $(n=1, 2, 3, \cdots )$
初項 $a_1$ が与えられたときの、 $S_{10} = \sum_{i=1}^{10} a_i$ を求める。

コード

import java.util.*;
public class aoj0055 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			double a = stdin.nextDouble();
			double sum = a;
			for(int i = 2; i <= 10; i++)
				sum += ((i&1)==1 ? (a /= 3.0) : (a *= 2.0));
			System.out.println(sum);
		}
	}
}

Goldbach's Conjecture(AOJ No. 0056)

グライバッハ予想(Goldbach's Conjecture)
　:4 以上の偶数は 2 つの素数の和で表すことができる
整数 $n$ が与えられたとき、 $n$ が素数の和で表したときの組み合わせ数を求める。

アルゴリズム

エラトステネスの篩で、
flag[i]:= iが素数かどうか
prime[j]:= j番目の素数
を求めておいて、一つ目の素数aをprime[j]から選ぶ。
二つ目の素数はflag[n-a]で調べる。
ただし、二つ目の素数を選ぶとき、n-a >= aかどうかを確かめる.
(n-aが正でないとflagのレンジ外になってしまうし、a以上の素数を選ばないと、組み合わせ数がダブって数えられてしまう)

import java.util.*;
public class aoj0056 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N_MAX = 50000;
	static final ArrayList<Integer> prime_array = new ArrayList<Integer>();
	static final boolean[] prime_flag = sieve(N_MAX);
	static boolean[] sieve(int n){
		boolean[] ret = new boolean[n+1];
		Arrays.fill(ret, true);
		ret[0] = ret[1] = false;
		for(int i = 2; i*i <= n; ++i)
			if(ret[i]) for(int j = i*i; j < n; j+=i) ret[j] = false;
		return ret;
	}
	
	public static void main(String[] args) {
		for(int i = 0; i <= N_MAX; ++i) if(prime_flag[i]) prime_array.add(i);		
		while(true){
			int n = stdin.nextInt();
			if(n == 0) break;
			System.out.println(solve(n));
		}
	}
	static int solve(int n){
		int res = 0;
		for(int a: prime_array){
			int b = n - a;
			if(a <= b && prime_flag[b]) res++;
		}
		return res;
	}
}

The Number of Area(AOJ No.0057)

平面上に直線がn本与えられたときの最大の領域数を求める。

アルゴリズム

最大領域数は $1 + n + m$ 。
$m$ は最大の接点数となっている( $m = {}_n C_{2}$ )。
これを計算して $\frac{n^2 + n + 2}{2}$ を出力する。
アルゴリズムでもなんでもないな...

コード

import java.util.*;
public class aoj0057 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			int n = stdin.nextInt();
			System.out.println((n*n+n+2)/2);
		}
	}
}

Orthogonal(AOJ No. 0058)

4つの点 $A(x_A , y_A ), B(x_B , y_B), C(x_C , y_C), D(x_D , y_D)$ が与えられたとき、
直線 $\vec{AB}$ と直線 $\vec{CD}$ が直交しているかどうかを判定する(※線分ではなく直線)。

コード

内積で判定、座標が実数なのでEPS使ってます。

import java.awt.geom.Point2D;
import java.util.*;

public class aoj0058 {
	static final Scanner stdin = new Scanner(System.in);
	static final double EPS = 1e-10;
	static boolean EQ(double a, double b){ return Math.abs(a-b) < EPS; }
	public static void main(String[] args) { new aoj0058(); }
	aoj0058(){
		while(stdin.hasNext()){
			double xA = stdin.nextDouble(), yA = stdin.nextDouble();
			double xB = stdin.nextDouble(), yB = stdin.nextDouble();
			double xC = stdin.nextDouble(), yC = stdin.nextDouble();
			double xD = stdin.nextDouble(), yD = stdin.nextDouble();
			System.out.println(
					EQ( dot(new Point(xA-xB, yA-yB), new Point(xC-xD, yC-yD)), 0.0 ) ?
							"YES" : "NO"
			);
		}
	}
	public class Point extends Point2D.Double{ //implements Comparable<Point>{
		private static final long serialVersionUID = -1781994971111328877L;
		//constructor
		public Point(){ super(); }
		public Point(double x, double y){ super(x,y); }
		public Point(Point p){ super(p.x, p.y); }
	} //class Point
	double dot(Point a, Point b) { return a.x*b.x + a.y*b.y; }
}

Intersection of Rectangles(AOJ No.0059)

四角形Aの左下の頂点の座標 $a1_x, a1_y )$ と右上の頂点の座標 $a3_x, a3_y )$ と
四角形Bの左下の頂点の座標 $b1_x, b1_y )$ と右上の頂点の座標 $b3_x, b3_y )$ が与えられたとき、
四角形A, 四角形Bが交差しているかどうかを求める（接しているものも重なっているとみなす）。

アルゴリズム1

(ライブラリのテスト)
1. 一方の四角形に他方の四角形の頂点が含まれている
2. 一方の四角形の辺と他方の四角形の辺が交わっている
1.2の項目を、四角形A,Bについて調べ、どれかを満たしていたら四角形A, Bが交差している

コード1

import java.awt.geom.*;
import java.util.*;
public class aoj0059 {
	static final Scanner stdin = new Scanner(System.in);
	static final Point[] A = new Point[4], B = new Point[4];
	static final Line[] LA = new Line[4], LB = new Line[4];
	static Solver solver = Solver.Solution1;
	public static void main(String[] args) { 
		while(stdin.hasNext()){
			Point a1 = new Point(stdin.nextDouble(), stdin.nextDouble());
			Point a3 = new Point(stdin.nextDouble(), stdin.nextDouble());
			Point b1 = new Point(stdin.nextDouble(), stdin.nextDouble());
			Point b3 = new Point(stdin.nextDouble(), stdin.nextDouble());
			System.out.println( solver.solve(a1, a3, b1, b3) ? "YES" : "NO");
		}
	}
	enum Solver {
		Solution1 { @Override boolean solve(Point a1, Point a3, Point b1, Point b3){ 
			B[0] = b1; B[2] = b3;
			B[1] = new Point(b1.x, b3.y); B[3] = new Point(b3.x, b1.y);
			A[0] = a1; A[2] = a3;
			A[1] = new Point(a1.x, a3.y); A[3] = new Point(a3.x, a1.y);

			for(Point b: B) if(contains(A, b)) return true;
			for(Point a: A) if(contains(B, a)) return true;

			for(int i = 0; i < 4; ++i){
				LA[i] = new Line(A[i], A[(i+1)%4]);
				LB[i] = new Line(B[i], B[(i+1)%4]);
			}
			for(Line lb: LB)
				for(Line la: LA)
					if(la.intersectsSS(lb)) return true;
			return false;
		}}, Solution2 { @Override boolean solve(Point a1, Point a3, Point b1, Point b3){
			return intersectsRR(new Point[]{a1, a3}, new Point[]{b1, b3});
		}}, Solution3{ @Override boolean solve(Point a1, Point a3, Point b1, Point b3){
			double ax = a1.x - EPS, bx = b1.x;
			double ay = a1.y - EPS, by = b1.y;
			double aw = a3.x - ax + EPS, bw = b3.x - bx;
			double ah = a3.y - ay + EPS, bh = b3.y - by;
			return new Rectangle2D.Double(ax, ay, aw, ah).intersects(bx, by, bw, bh);
		}};
		boolean solve(Point a1, Point a3, Point b1, Point b3){ return false; }
	}
	public static final double EPS = 1e-10;
	public static boolean equal(double a, double b){ return Math.abs(a-b) < EPS; }	// a == b
	public static boolean less(double a, double b){ return a - b < -EPS; }			// a < b
	public static boolean leq(double a, double b){ return a - b < EPS; }			// a <= b
	public static boolean greater(double a, double b){ return less(b,a); }			// a > b
	@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 double normsq(){ return x*x + y*y; }
		public final Point sub(Point p){ return new Point( x - p.x, y - p.y ); }
		public final double cross(Point p){ return x * p.y - y * p.x; }
		public final double dot(Point p){ return x * p.x + y * p.y; }
		public final int ccw(Point b, Point c) {
			Point ab = b.sub(this);
			Point ac = c.sub(this);
			if (greater(ab.cross(ac), 0))		return +1;	// counter clockwise
			if (less(ab.cross(ac), 0))			return -1;	// clockwise
			if (less(ab.dot(ac), 0))			return +2;	// (c--a--b or b--a--c) on line
			if (less(ab.normsq(), ac.normsq()))	return -2;	// (a--b--c or c--b--a) on line (b≠c, includes a=b)
			return 0;									// (a--c--b or b--c--a) on line (includes c=b, a=c, a=b=c)
		}
	} //class Point
	public static class Line{
		private final Point start;
		private final Point end;
		public Line(Point start, Point end){ this.start = new Point(start); this.end = new Point(end); }
		public final int ccw(Point p){ return start.ccw(end, p); }
		public final boolean intersectsSS(Line t) {
			return ccw(t.start) * ccw(t.end) <= 0 && t.ccw(start) * t.ccw(end) <= 0;
		}
	} //class Line
	public static boolean contains(Point[] polygon, Point p) {
		boolean in = false;
		for (int i = 0, n = polygon.length; i < n; ++i) {
			Point a = polygon[i].sub(p), b = polygon[(i+1)%n].sub(p);
			if (a.y > b.y){ Point temp = b; b = a; a = temp; }
			if (a.y <= 0 && 0 < b.y)
				if (a.cross(b) < 0) in = !in; //=0 -> a//b -> on 
			if (equal(a.cross(b), 0) && leq(a.dot(b), 0)) return true; //on edge
		}
		return in; //in out
	}
	public static final boolean intersectsRR(Point[] a, Point[] b){
		return leq(a[0].x, b[1].x) && leq(a[0].y, b[1].y) && leq(b[0].x, a[1].x) && leq(b[0].y, a[1].y);
	}
}

アルゴリズム2

通常これでやればおｋ
$a1_x \leq b3_x \wedge a1_y \leq b3_y \wedge b1_x \leq a3_x \wedge b1_y \leq a3_y$ で判定

コード2

Solution2 { @Override boolean solve(Point a1, Point a3, Point b1, Point b3){
	return intersectsRR(new Point[]{a1, a3}, new Point[]{b1, b3});
}}, //abbr.

アルゴリズム3
Rectangel2D.Doubleのintersectsメソッドを使ってやるのが一番楽。
ただし、intersectsは接しているとき、交差しているとみなさないので、
一方の四角形を少し大きくしてやる。

Solution3{ @Override boolean solve(Point a1, Point a3, Point b1, Point b3){
	double ax = a1.x - EPS, bx = b1.x;
	double ay = a1.y - EPS, by = b1.y;
	double aw = a3.x - ax + EPS, bw = b3.x - bx;
	double ah = a3.y - ay + EPS, bh = b3.y - by;
	return new Rectangle2D.Double(ax, ay, aw, ah).intersects(bx, by, bw, bh);
}};

Card Game(AOJ No.0060)

1〜10のカードを使い２人でカードゲームをする。
お互いにカードを2枚カードを引き、1枚を表に、もう1枚を裏にしておく。
そして、両人はさらにもう一枚カードを引いても良い。
引いたカードの数字の和が20以下で、相手のカード数字の和より大きければ勝ち。
自分が引いたカードの数字a, bと相手が表にしてあるカードの数字cが与えられ、
さらにもう一枚引いたとき20以下になる確率が50%以上なら、カードをもう一枚引くことにする。
このルールに従うとき、カードをもう一枚引くかどうかを答える。

アルゴリズム

場に伏せてあるカードがなんであろうと、求める確率は変わらない。
$U=\{ 1, 2, \cdots , 10\}$
$X= U-\{ a, b, c\}$
とすれば、 $\frac{|\{ x | x\in X, x\leq 20-(a+b)\} |}{|X|}$ が0.5以上ならカードを引く。

コード

import java.util.*;
public class aoj0060 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		boolean[] talon = new boolean[11];
		while(stdin.hasNext()){
			Arrays.fill(talon, true);
			int a = stdin.nextInt();
			int b = stdin.nextInt();
			int c = stdin.nextInt();
			int sum = 0;
			talon[a] = talon[b] = talon[c] = false;
			for(int i = 0; i < talon.length; ++i)
				if(talon[i] && i < 20-a-b) sum++;
			System.out.println( 100 * sum / 7 >= 50 ? "YES" : "NO");
		}
	}
}

kanetaiの二次記憶装置

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

Differential II(AOJ No.0051), Factorial II(AOJ No.0052), Sum of Prime Numbers(AOJ No.0053), Sum of Nth decimal places(AOJ No.0054), Sequence(AOJ No.0055), Goldbach's Conjecture(AOJ No.0056), The Number of Area(AOJ No.0057), Orthogonal(AOJ No. 0058), Inter

Differential II(AOJ No.0051)

コード

Factorial II(AOJ No. 0052)

アルゴリズム

コード

Sum of Prime Numbers(AOJ No.0053)

コード

Sum of Nth decimal places(AOJ No.0054)

アルゴリズム

コード

Sequence(AOJ No.0055)

コード

Goldbach's Conjecture(AOJ No. 0056)

アルゴリズム

The Number of Area(AOJ No.0057)

アルゴリズム

コード

Orthogonal(AOJ No. 0058)

コード

Intersection of Rectangles(AOJ No.0059)

アルゴリズム1

コード1

アルゴリズム2

コード2

Card Game(AOJ No.0060)

アルゴリズム

コード