Sport Meet(AOJ No.0161), Hamming Numbers(AOJ No.0162), Highway Toll(AOJ No.0163), Ohajiki Game(AOJ No.0164), Lottery(AOJ No.0165), Area of Polygon(AOJ No.0166)

Sport Meet(AOJ No.0161)

nチームのレースの成績データ $(id, m_0, s_0, m_1, s_1, m_2, s_2, m_3, s_3)$ の形式で与えられる。
id：チーム名
$m_i, s_i :i$ 番目のレースのタイム分、秒
４つのレースのタイム合計で順位を決め優勝、準優勝、ブービー賞のチーム名を答える。
制約
$1\leq id \leq 1,000,000$
$4\leq n \leq 1,000,000$
タイム合計が同一にはならないような入力になっている。

コード

import java.util.*;
public class aoj0161 {
	static final Scanner stdin = new Scanner(System.in);
	static class T implements Comparable<T>{
		int id, sec;
		T(int id, int sec){ this.id = id; this.sec = sec; }
		@Override public int compareTo(T o) { return sec - o.sec; }
	}
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			T[] a = new T[n];
			for (int i = 0; i < n; i++)
				a[i] = new T(stdin.nextInt(), 
					60 * stdin.nextInt() + stdin.nextInt() + 
					60 * stdin.nextInt() + stdin.nextInt() +
					60 * stdin.nextInt() + stdin.nextInt() +
					60 * stdin.nextInt() + stdin.nextInt());
			Arrays.sort(a);
			System.out.println(a[0].id);
			System.out.println(a[1].id);
			System.out.println(a[n-2].id);
		}
	}
}

Hamming Numbers(AOJ No.0162)

ハミング数(Hamming numbers)
1に2,3,5を何回か(0回以上)かけ算して得られる数
n,mが与えられて、n以上m以下のハミング数の数を答える。
制約
$1\leq n \leq m \leq N = 1,000,000$

アルゴリズム

$isHammingNumber_{i}:= i$ がハミング数であるかどうか
$isHammingNumber_{0}=false, isHammingNumber_{1}=true$ と初期化しておけば、
$1 < i \leq N$ について、

$i\equiv 2 \pmod 2 \wedge isHammingNumber_{i/2}=true \rightarrow isHammingNumber_{i}=true$
$i\equiv 3 \pmod 3 \wedge isHammingNumber_{i/3}=true \rightarrow isHammingNumber_{i}=true$
$i\equiv 5 \pmod 5 \wedge isHammingNumber_{i/5}=true \rightarrow isHammingNumber_{i}=true$
otherwise $\rightarrow isHammingNumber_{i}=false$

と行った感じで、 $O(N)$ でiがハミング数であるかのテーブルが作れる。
同時に0〜iまでのハミング数の数を記録していけば、 $n,m$ が与えられてから答えが $O(1)$ で求まる。

コード

forループのところ< Nって書いてWAだした。N = 1000001とするように習慣付けといた方が変なところでWA出さなくてすみそうだ。

import java.util.*;
public class aoj0162 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 1000000;
	static final boolean[] isHammingNumber = new boolean[N+1];
	static final int[] LUT = new int[N+1];
	static final void init(){
		Arrays.fill(isHammingNumber, false);
		isHammingNumber[1] = true;
		LUT[0] = 0; LUT[1] = 1;
		for (int i = 2; i <= N; i++) {
			if(i%2 == 0 && isHammingNumber[i/2]) isHammingNumber[i] = true;
			if(i%3 == 0 && isHammingNumber[i/3]) isHammingNumber[i] = true;
			if(i%5 == 0 && isHammingNumber[i/5]) isHammingNumber[i] = true;
			LUT[i] = LUT[i-1] + (isHammingNumber[i] ? 1 : 0);
		}
	}
	public static void main(String[] args) {
		init();
		int n, m;
		while((n = stdin.nextInt()) != 0){
			m = stdin.nextInt();
			System.out.println(LUT[m]-LUT[n-1]);
		}
	}
}

Highway Toll(AOJ No.0163)

料金表と、
出発IC番号, 出発IC通過時刻 h m
到着IC番号, 到着IC通過時刻 h m
が与えられて、必要料金を答える。
ただし、17時30分〜19時30分までに出発ICか到着ICを通過し、なおかつ走行距離が40km以下の車に対する通行料金は半額になる。※料金は50円単位とし、端数は切り上げ。
※出発IC通過時刻 < 17時30分かつ19時30分<到着IC通過時刻なら半額対象外

コード

料金表写し間違えてWAだした。料金表も入力する形式にしてくれればいいのに。

import java.util.*;
public class aoj0163 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 7;
	static final int[][] table = new int[][]{
		{0, 300, 500, 600, 700, 1350, 1650}, 
		{6,   0, 350, 450, 600, 1150, 1500}, 
		{13,  7,   0, 250, 400, 1000, 1350}, 
		{18,  12,  5,   0, 250,  850, 1300}, 
		{23,  17, 10,   5,   0,  600, 1150}, 
		{43,  37, 30,  25,  20,    0,  500}, 
		{58,  52, 45,  40,  35,   15,    0}
	};
	static final int length[][] = new int[N][N];
	static final int fee[][] = new int[N][N];
	static final int A = 17*60+30; //17h30m
	static final int B = 19*60+30; //19h30m
	static final void init(){
		for (int i = 0; i < N; i++)
			for (int j = i; j < N; j++) {
				fee[i][j] = fee[j][i] = table[i][j];
				length[i][j] = length[j][i] = table[j][i];
			}
	}
	static final int discount(int fee){
		fee /= 2;
		int temp = fee % 50;
		if(temp > 0) fee += 50 - temp;
		return fee;
	}
	public static void main(String[] args) {
		init();
		int src, dst, stime, dtime;
		while((src = stdin.nextInt()-1) >= 0){
			stime = stdin.nextInt()*60 + stdin.nextInt();
			dst = stdin.nextInt()-1;
			dtime = stdin.nextInt()*60 + stdin.nextInt();
			System.out.println(
					(length[src][dst] <= 40 && (A <= stime && stime <= B) || (A <= dtime && dtime <= B)) ? 
							discount(fee[src][dst]) : fee[src][dst]
			);
		}
	}
}

Ohajiki Game(AOJ No.0164)

1,2,3,4からなる数列 $(a_i)_{i=1,2, \cdots n-1}$ が与えられる。
山に32個のおはじきがある。山のおはじきの数を $m$ 個としたとき
$i$ ターン目に一郎が山から $(m-1)\bmod 5$ 個おはじきをとる->次郎が山から $a_{i\pmod{n}}$ 個おはじきをとる。
という操作を繰り返すので山の数をシミュレートする。

コード

import java.util.*;
public class aoj0164 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = stdin.nextInt();
			int b = 32;
			for(int i = 0; b > 0; i = (i+1)%n) {
				b -= (b-1)%5;
				System.out.println(b);
				b -= a[i];
				System.out.println(b >= 0 ? b : 0);
			}
		}
	}
}

Lottery(AOJ No.0165)

ありえないほど問題が長いので、要約。
$p_i$ と $m_i$ が $n$ 個与えられる。
区間[ $p_i -m_i , p_i +m_i$ ]の区間にある素数の個数(ただし、 $10^6$ 以上の素数はない物として扱う)を $x_i$ とする。
$y_i = \left\{ \begin{array}{lr} -1 & (x_i =0) \\ x_i -1 & (otherwise) \end{array} \right.$
$ans = \sum_{i=1}^n y_i$

コード

問題長過ぎる

import java.util.*;
public class aoj0165 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 1000000;
	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;
	}
	public static void main(String[] args) {
		boolean[] isPrime = sieve(N+1);
		int[] LUT = new int[N+1];
		LUT[0] = 0;
		for(int i = 1; i <= N; ++i) LUT[i] = LUT[i-1] + (isPrime[i] ? 1 : 0);
		int n;
		while((n = stdin.nextInt()) != 0){
			int ans = 0;
			for (int i = 0; i < n; i++) {
				int p = stdin.nextInt(), m = stdin.nextInt();
				int x = LUT[Math.min(N, p + m)] - LUT[Math.max(1, p - m)-1];
				ans += (x == 0 ? -1 : x - 1);
			}
			System.out.println(ans);
		}
	}
}

Area of Polygon(AOJ No.0166)

ある円に内接する２つの多角形の頂点情報が与えられる。
頂点情報は、ある頂点から反時計回りにx度回転した位置に次の頂点があるという形式で与えられる。
２つの多角形の面積の大小関係を答える。

アルゴリズム

円の半径をrとすると多角形の面積は、 $\frac{1}{2}r^2 \sum_i \sin x_i\frac{\Pi}{180}$
で与えられる。
大小関係を求めるだけなら $\frac{1}{2}r^2$ は不要。

コード

常に反時計回りで与えられるので、絶対値を考えたりする必要は無いが、最後の頂点と最初の頂点と中心からなる三角形の面積を忘れないように足す。

import java.util.*;
public class aoj0166 {
	static final Scanner stdin = new Scanner(System.in);
	public static final double EPS = 1e-10;
	public static final boolean equal(double a, double b){ return Math.abs(a-b) < EPS; }// a == b
	public static void main(String[] args) {
		int m;
		while((m = stdin.nextInt()) != 0){
			double a = 0, b = 0, c = 360;
			while(--m > 0){
				int x = stdin.nextInt();
				a += Math.sin(x*Math.PI/180);
				c -= x;
			}
			a += Math.sin(c*Math.PI/180);
			int n = stdin.nextInt(); c = 360;
			while(--n > 0){
				int x = stdin.nextInt();
				b += Math.sin(x*Math.PI/180);
				c -= x;
			}
			b += Math.sin(c*Math.PI/180);
			System.out.println(equal(a, b) ? 0 : a > b ? 1 : 2);
		}
	}
}

kanetaiの二次記憶装置

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

Sport Meet(AOJ No.0161), Hamming Numbers(AOJ No.0162), Highway Toll(AOJ No.0163), Ohajiki Game(AOJ No.0164), Lottery(AOJ No.0165), Area of Polygon(AOJ No.0166)

Sport Meet(AOJ No.0161)

コード

Hamming Numbers(AOJ No.0162)

アルゴリズム

コード

Highway Toll(AOJ No.0163)

コード

Ohajiki Game(AOJ No.0164)

コード

Lottery(AOJ No.0165)

コード

Area of Polygon(AOJ No.0166)

アルゴリズム

コード