kanetaiの二次記憶装置

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

Doctor's Memorable Codes(AOJ No.0111), A Milk Shop(AOJ No.0112), Period(AOJ No.0113), Electro-Fly(AOJ No.0114)

Online Judge

リポジトリ

Doctor's Memorable Codes(AOJ No.0111)

文字→固定長01系列, 可変長(0〜3)01系列→文字列の変換表が与えられて、それに従って、暗号文字列をデコードする。
可変長10系列→文字列の変換表に含まれないものがあれば、残りは切り捨てる。

コード

可変長10系列→文字列の変換表に含まれないのが、末尾にある場合は、問題文の例で分かるが、
途中にそのような系列がくる場合などの指示がないので、問題記述不十分。
可変長10系列→文字列の変換表に含まれないものが出現すれば、残りは切り捨てればおkだった。

import java.util.*;
public class aoj0111 {
	static final Scanner stdin = new Scanner(System.in);
	static final HashMap<Character, String> atoc = new HashMap<Character, String>();
	@SuppressWarnings("serial") static final HashMap<String, Character> ctoa = new HashMap<String, Character>(){
		{
			put("101", 	' ');	put("0101",	'C');	put("0110", 	'K');	put("00110",	'S');
			put("000000", 	'\'');	put("0001", 	'D');	put("00100", 	'L');	put("00111",	'T');
			put("000011", 	',');	put("110",	'E');	put("10011001",	'M');	put("10011100",	'U');
			put("10010001", '-');	put("01001", 	'F');	put("10011110",	'N');	put("10011101",	'V');
			put("010001", 	'.');	put("10011011",	'G');	put("00101",	'O');	put("000010",	'W');
			put("000001", 	'?');	put("010000",	'H');	put("111",	'P');	put("10010010",	'X');
			put("100101", 	'A');	put("0111",	'I');	put("10011111",	'Q');	put("10010011",	'Y');
			put("10011010", 'B');	put("10011000",	'J');	put("1000",	'R');	put("10010000",	'Z');
		}
	};
	public static void main(String[] args) {
		for(int i = 0; i <= 31; ++i){
			char c;
			switch(i){
			case 26: c = ' '; break;
			case 27: c = '.'; break;
			case 28: c = ','; break;
			case 29: c = '-'; break;
			case 30: c = '\''; break;
			case 31: c = '?'; break;
			default: c = (char)('A'+i);
			}
			StringBuilder str = new StringBuilder();
			for(int j = 0; j < 5; ++j) str.append( (char)(((i>>j) & 1) + '0') );
			atoc.put(c, str.reverse().toString());
		}
		while(stdin.hasNext()){
			char[] in = stdin.nextLine().toCharArray();
			StringBuilder code = new StringBuilder();
			for(char ch: in) code.append(atoc.get(ch));
			LOOP:
			while(3<=code.length()){
				for(int i=3; i <= 8; ++i){
					if(i > code.length()) break LOOP;
					String k = code.substring(0,i);
					if(ctoa.containsKey(k)){
						System.out.print(ctoa.get(k));
						code.delete(0, i);
						continue LOOP;
					}
				}
				break;
			}
			System.out.println("");
		}
	}
}

A Milk Shop(AOJ No.0112)

n人の人が並んでいて、一つの蛇口からミルクを受け取る。
それぞれが蛇口からミルクを受け取るのに要する時間 x_iが与えられたとき、
人の並びを入れ替えて、それぞれの待ち時間の合計の最小値を求める。
制約
1\leq n\leq 10000
1\leq x_i \leq 60

アルゴリズム

\{x_i|1\leq i \leq n\}をソートしたもののi番目の要素を y_iとすると、求める値は、
\sum_{i=1}^{n-1} \sum_{j=1}^{i} y_i
簡単だけど、
\sum_{i=1}^{n-1} \sum_{j=1}^{i} 60 = 60\sum_{i=1}^{n-1} i = \frac{60(n^2 - n)}{2} = 30(10^8 - 10^4)=2,999,700,000
なので、int(-2,147,483,648 〜 2,147,483,647)ではまずいと気づけるかな？という問題。
おいらは気づかなかったけどwww

コード

import java.util.*;
public class aoj0112 {
	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[] l = new int [n];
			for(int i = 0; i < n; ++i) l[i] = stdin.nextInt();
			Arrays.sort(l);
			long sum = 0, ans = 0;
			for(int i = 0; i < n; ++i){
				ans += sum;
				sum += l[i];
			}
			System.out.println(ans);
		}
	}
}

Period(AOJ No.0113)

p, qが与えられたとき、の小数部分を答える。
循環小数の場合、循環しているところを'^'で示す。
制約
0 < p < q < 10^6

アルゴリズム

問題に書いてある通り、普通に筆算してくだけ。
余りが小数点以下何桁目で出てきたかを覚えておいて、同じ余りが出てきたら、
前回出てきたところから現在のところまでの桁が循環する。

コード

import java.util.*;
public class aoj0113 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			int p = stdin.nextInt(), q = stdin.nextInt();
			StringBuilder ans = new StringBuilder();
			HashMap<Integer, Integer> found = new HashMap<Integer, Integer>();
			found.put(0,0);
			while(true){
				ans.append(p / q);
				p %= q;
				if(found.containsKey(p)) break;
				else found.put(p, ans.length());
				p *= 10;
			}
			System.out.println(ans.substring(1));
			if(p == 0) continue;
			for(int i = 1; i < ans.length(); ++i) System.out.print( i < found.get(p) ? ' ' : '^');
			System.out.println("");
		}
	}
}

Electro-Fly(AOJ No.0114)

\left\{ \begin{array}{c} x_{k+1} = a_1 x_k \bmod m_1 \\ y_{k+1} = a_2 y_k \bmod m_2 \\ z_{k+1} = a_3 z_k \bmod m_3 \end{array} \right.
で移動する。
[ x_0 , y_0, z_0 ] ^T = [ 0, 0, 0] ^T としたとき、 k>0で [ 0, 0, 0] ^T になる kを求める。
制約
1 < a_1, m_1, a_2, m_2, a_3, m_3 < 2^{15}
a_1と m_1, a_2と m_2, a_3と m_3は互いに素(必ず [ 0, 0, 0] ^T に戻ってくる)

アルゴリズム

x, y, zそれぞれ、個別に、1にもどる周期 p_x, p_y, p_zとすると、 0 < p_i < m_i = 2^{15}になる。
x, y, z同時に1になる周期を求めようとすると、かなり大きな値になりそうなのが予想できるので、
まず、 p_x, p_y, p_zを求めておいて、そこから、最小公倍数を求める。
LCM(p_x, p_y, p_z)

コード

最大公約数が小さいとき、最小公倍数が大きくなりやすい。
３数の最大公約数を求めるから、 2^{15} \times 2^{15} \times 2^{15} = 2^{45}ぐらいの値になるかもしれない。int→longにした。
もしかすると、LCMを求めるとき、計算順序を考えれば(a/GCD(a,b)*bとか)、intでもいいかもしれない。

import java.util.*;
public class aoj0114 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int[] a = new int[3], m = new int[3];
		long[] p = new long[3];
		while(true){
			for(int i = 0; i < 3; ++i){
				a[i] = stdin.nextInt();
				m[i] = stdin.nextInt();
			}
			if(a[0] == 0) break;
			for(int i = 0; i < 3; ++i) p[i] = getPeriod(a[i], m[i]);
			System.out.println( LCM(p) );
		}
	}
	static int getPeriod(int a, int m){
		int x = 1, res = 0;
		do{
			x = (x*a) % m;
			res++;
		}while(x != 1);
		return res;
	}
	static long GCD(long a, long b){ return b == 0 ? a : GCD(b, a%b); }
	static long GCD(long[] x){
		long ret = x[0];
		for(int i = 1; i < x.length; ++i) ret = GCD(ret, x[i]);
		return ret;
	}
	static long LCM(long a, long b){ return a / GCD(a, b) * b; }
	static long LCM(long[] x){
		long ret = x[0];
		for(int i = 1; i < x.length; ++i) ret = LCM(ret, x[i]);
		return ret;
	}
}