kanetaiの二次記憶装置

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

Reverse Sequence(AOJ No.0006), Debt Hell(AOJ No.0007), Sum of 4 Integers(AOJ No.0008), Prime Number(AOJ No.0009)

リポジトリ

Reverse Sequence(AOJ No.0006)

タイトルの通り

import java.util.*;
public class aoj0006 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		System.out.println( new StringBuilder(stdin.nextLine()).reverse().toString() );
	}
}

Debt Hell(AOJ No.0007)

週5%の利子に加え、1000円未満を切り上げる。はじめの借金が10万円のときn週後の借金を求める。

import java.util.*;
public class aoj0007 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n = stdin.nextInt();
		double m = 100000;
		while(n-- > 0){
			m = m + m*0.05;
			if(m%1000 != 0) m = m - m % 1000 + 1000; 
		}
		System.out.println((int)m);
	}
}

Sum of 4 Integers(AOJ No.0008)

 a+b+c+d=nとなる整数解 (a,b,c,d)の組み合わせの数を求める。
制約
 n\leq 50
 0\leq a,b,c,d \leq 9

ごり押しでいける(10^4)。

import java.util.*;
public class aoj0008 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			int n = stdin.nextInt(), ans = 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;
			System.out.println(ans);
		}
	}
}

Prime Number(AOJ No.0009)

 n以下の素数の数を求める
制約
 n\leq 999999

アルゴリズム

エラトステネスの篩で素数表を作成しておいて素数の数を数える。(素数、約数)

コード

ライブラリとして作ったのが、boolean配列だったのでそのまま流用しているが、
BitSetにしておくと、下のようにn bit mask→cardinalityで数えられる。

import java.util.*;
public class aoj0009 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 1000001;
	public static void main(String[] args) {
		boolean[] tempTable = sieve(N);
		BitSet table = new BitSet(N), mask = new BitSet(N);
		for(int i = 0; i < N; i++) table.set(i, tempTable[i]);
		while(stdin.hasNext()){
			mask.clear();
			mask.set(0, stdin.nextInt()+1 );
			mask.and(table);
			System.out.println( mask.cardinality() );
		}
	}
	public static final boolean[] sieve(int n){
		boolean[] ret = new boolean[n]; 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;
	}
}