kanetaiの二次記憶装置

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

Hit and Blow(AOJ No.0226), Thanksgiving(AOJ No.0227), Seven Segments(AOJ No.0228), Big Hit !(AOJ No.0229), Ninja Climbing(AOJ No.0230), Dangerous Bridge(AOJ No.0231)

Online judge

リポジトリ

Hit and Blow(AOJ No.0226)

hitとblowの数を答える。Hit and Blow(AOJ No.0025)とほぼ同じ

コード

ソートしてindexを勧めながらblowを数える

import java.util.*;
public class aoj0226 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			char[] a = stdin.next().toCharArray(), b = stdin.next().toCharArray();
			if (a[0] == '0' && b[0] == '0') break;
			int hit = 0, blow = 0;
			for(int i=0; i < a.length; ++i) if(a[i] == b[i]) ++hit;
			Arrays.sort(a); Arrays.sort(b);
			int ai = 0, bi =0;
			while( ai < a.length && bi < b.length ){
				if(a[ai] == b[bi]){ ++blow; ++ai; ++bi; }
				else if(a[ai] > b[bi]) ++bi;
				else ++ai;
			}
			blow -= hit;
			System.out.println(hit + " " + blow);
		}
	}
}

Thanksgiving(AOJ No.0227)

購入する野菜の個数 n、袋に入る野菜の個数 m、各野菜の値段 p_1, p_2, \cdots, p_nが与えられる。

  • 1 つの袋には m 個まで野菜を詰められる。
  • 野菜が m 個詰めてある袋については、その中で最も安い野菜が無料となる。
  • 野菜の個数が m 個に達しない袋は割引の対象外。

n個の野菜全てを買ったときの最小の値段を求める。
制約
1\leq n, m \leq 1,000
10 \leq p_i 10,000

コード

グリーディに高いものから袋に入れてけばおk

import java.util.*;
public class aoj0227 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt(), m = stdin.nextInt();
			if ((n|m) == 0) break;
			int p[] = new int[n];
			for (int i = 0; i < n; ++i) p[i] = stdin.nextInt();
			Arrays.sort(p);
			int ans = 0;
			for (int i = 1; i <= n; ++i) {
				if (i % m == 0) continue;
				ans += p[n-i];
			}
			System.out.println(ans);
		}
	}
}

Seven Segments(AOJ No.0228)

http://judge.u-aizu.ac.jp/onlinejudge/IMAGE2/7segments.png
上図のような７セグメントの点灯を7bitの信号で行う。1になっているbitのセグメントの点灯/消灯の切り替えられる。
0〜9の数字がn個与えられる。
何も点灯していない状態から、与えられたn個の数字を順番に点灯するのに必要な7bit信号(n個)を答える。
制約
0 < n < 101

コード

intのxorで信号を決める。てかBitSetって、String -> BitSetの変換できないのか...

import java.util.*;
public class aoj0228 {
	static final Scanner stdin = new Scanner(System.in);
	static final String[] seg = { "0111111", "0000110", "1011011", "1001111", "1100110", "1101101", "1111101", "0100111", "1111111", "1101111",  };
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == -1) break;
			int a = 0;
			while (n-- > 0) {
				int b = Integer.valueOf(seg[stdin.nextInt()], 2);
				System.out.println(toString(a^b));
				a = b;
			}
		}
	}
	static String toString(int i) {
		StringBuilder sb = new StringBuilder(Integer.toBinaryString(i)).reverse();
		while (sb.length() < 7) sb.append('0');
        return sb.reverse().toString();
    }
}

Big Hit !(AOJ No.0229)

要するに、b, r, g, c, s, tが与えられて、
95b + 63r + 7g + 2c + 3s - 3t + 100と答える。

コード

import java.util.*;
public class aoj0229 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int b = stdin.nextInt(), r = stdin.nextInt(), g = stdin.nextInt(), c = stdin.nextInt(), s = stdin.nextInt(), t = stdin.nextInt();
			if ((b|r|g|c|s|t) == 0) break;
			System.out.println(95*b + 63*r + 7*g + 2*c + 3*s - 3*t + 100);
 		}
	 }
}

Ninja Climbing(AOJ No.0230)

高さnのビルの壁の状態が与えられて、それを三角とびの要領でジャンプして最上階までいくことを考える。
壁の状態

  • 0. 普通の壁:上下の移動はしない。次のジャンプはそこから行う。
  • 1. はしご :はしごは 2 つ以上の階にまたがってかかっており、今いるはしごの一番上まで移動する。次のジャンプはそこから行う。
  • 2. すべる壁:普通の壁かはしごの一番上まで滑り落ちる。次のジャンプはそこから行う。

ジャンプ はどちらか一方のビルの1階から始められる。向かい側のビルへジャンプするときには、同じ階・1つ上の階・2 つ上の階の、いずれかに飛び移ることができる。
最上階にたどり着けるかどうかを答える。
制約
2 < n < 101

コード

幅優先

import java.util.*;
public class aoj0230 {
	static final Scanner stdin = new Scanner(System.in);
	static final int NORMAL = 0, LADDER = 1, SLIPPY = 2, ID = 0, FLOOR = 1, COST = 2;
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			int b[][] = new int[2][n];
			for (int i = 0; i < 2; ++i) for (int j = 0; j < n; ++j) b[i][j] = stdin.nextInt();
			System.out.println(solve(b, n));
		}
	}
	static String solve(int[][] b, int n) {
		Queue<int[]> q = new LinkedList<int[]>();
		boolean[][] closed = new boolean[2][n];
		q.add(new int[]{0, 0, 0});
		q.add(new int[]{1, 0, 0});
		while (!q.isEmpty()) {
			int[] p = q.poll();
			if (b[p[ID]][p[FLOOR]] == LADDER) {
				while (p[FLOOR] < n && b[p[ID]][p[FLOOR]] == LADDER) ++p[FLOOR];
				--p[FLOOR]; //行き過ぎた分戻る
			} else if (b[p[ID]][p[FLOOR]] == SLIPPY) {
				while (b[p[ID]][p[FLOOR]] == SLIPPY) --p[FLOOR];
			}
			
			if (closed[p[ID]][p[FLOOR]]) continue;
			closed[p[ID]][p[FLOOR]] = true;
			if (p[FLOOR] == n - 1) return ""+p[COST];
			
			for (int i = 0; i < 3; ++i) if (n > p[FLOOR] + i) q.add(new int[]{ (p[ID]+1)%2, p[FLOOR] + i, p[COST] + 1 });
		}
		return "NA";
	}
}

Dangerous Bridge(AOJ No.0231)

150kgまで耐えられる橋がある。
橋を渡る通行人の人数 n、各通行人の体重 m_i、橋を渡り始める時刻 a_i、渡り終える時刻 b_i が与えられたとき、橋が壊れるかどうかを答える。
制約
0 < n, m < 101
0 \leq a, b\leq 2^{31}

コード

\{ m_i, a_i\} と \{ -m_i, b_i\} を配列に入れて時間でソートし、シミュレートする

import java.util.*;
public class aoj0231 {
	static final Scanner stdin = new Scanner(System.in);
	static final int LIMIT = 150, MASS = 0, TIME = 1, N = 2;
	public static void main (String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			int[][] array = new int[n+n][N];
			for (int i = 0; i < n+n; i+=2) {
				int m = stdin.nextInt(), a = stdin.nextInt(), b = stdin.nextInt();
				array[i] = new int[]{m, a};
				array[i+1] = new int[]{-m, b};
			}
			Arrays.sort(array, new Comparator<int[]>() {
				@Override public int compare(int[] a, int[] b) { return a[TIME] != b[TIME] ? a[TIME] - b[TIME] : a[MASS] - b[MASS]; }
			});
			String ans = "OK";
			int weight = 0;
			for (int[] t : array) {
				weight += t[MASS];
				if (weight > LIMIT) { ans = "NG"; break; }
			}
			System.out.println(ans);
		}
	}
}