数作り

学籍番号の末尾4個の数字を，順序を変えずに使用する
演算記号は，四則演算(+, -, *, /) と括弧のみを使用する
除算は最終的に，割り切れなければならない
0〜20の整数作成を目指す

例
0 = 201 * 0
1 = 2 - 01 + 0
2 = 20 / 10
3 = 2 + 01 + 0
8 = -2 + 010
10 = 20 - 10
12 = 2 + 010
19 = 20 - 1 + 0
20 = 2 * 010
他はできない

Digit count: 
4
Digit data(ex. 2 0 1 0): 
2
0
1
0
All Expressions Count: 5936
   0 = ( 2 * ( 0 * ( 1 + 0 ) ) ) [1188 patterns]
   1 = ( 2 - ( 0 + ( 1 + 0 ) ) ) [240 patterns]
   2 = ( 2 * ( 0 + ( 1 + 0 ) ) ) [730 patterns]
   3 = ( 2 + ( 0 + ( 1 + 0 ) ) ) [176 patterns]
   4 = (Impossible)
   5 = (Impossible)
   6 = (Impossible)
   7 = (Impossible)
   8 = ( (-2) + ( 0 + 10 ) ) [18 patterns]
   9 = (Impossible)
  10 = ( ( 2 * 0 ) + 10 ) [10 patterns]
  11 = (Impossible)
  12 = ( 2 + ( 0 + 10 ) ) [18 patterns]
  13 = (Impossible)
  14 = (Impossible)
  15 = (Impossible)
  16 = (Impossible)
  17 = (Impossible)
  18 = (Impossible)
  19 = ( 20 - ( 1 + 0 ) ) [16 patterns]
  20 = ( 20 * ( 1 + 0 ) ) [58 patterns]

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

public class AlgoTask {
	
	private static int PRINT_MIN = 0;
	private static int PRINT_MAX = 20;

	private static class Entry {
		private double result;
		private String expr;

		public Entry(double result, String expr) {
			this.result = result;
			this.expr = expr;
		}

		public Entry(int i) {
			this.result = i;
			this.expr = String.valueOf(i);
		}

		public Entry connect(Entry rh) {
			return new Entry(result * 10 + rh.result, expr + rh.expr);
		}

		public Entry negative() {
			return new Entry(-result, "(-" + expr + ")");
		}

		public Entry add(Entry rh) {
			return new Entry(result + rh.result, "( " + expr + " + " + rh.expr
					+ " )");
		}

		public Entry sub(Entry rh) {
			return new Entry(result - rh.result, "( " + expr + " - " + rh.expr
					+ " )");
		}

		public Entry mul(Entry rh) {
			return new Entry(result * rh.result, "( " + expr + " * " + rh.expr
					+ " )");
		}

		public Entry div(Entry rh) {
			return new Entry(result / rh.result, "( " + expr + " / " + rh.expr
					+ " )");
		}

		@Override
		public String toString() {
			return result + ": " + expr;
		}
	}

	/**
	 * ビット列の中から1の数を返す。
	 * 
	 * @param bits
	 *            ビット列
	 * @return 1の数
	 */
	private static int count1(int bits) {
		int count = 0;
		while (bits != 0) {
			if ((bits & 0x1) == 0x1) {
				count++;
			}
			bits >>>= 1;
		}
		return count;
	}

	/**
	 * 数列に対してスタック命令列を試す。
	 * @param nums 入力数列
	 * @param insts push:1 pop:0 の命令ビット列
	 * @return 全通りの結果。失敗したら空リスト。
	 */
	private static List<Entry> processInsts(List<Entry> nums, int insts) {
		Deque<Entry> input = new ArrayDeque<Entry>(nums);
		Deque<List<Entry>> stack = new ArrayDeque<List<Entry>>();
		int instsLen = nums.size() * 2 - 1;
		for (int i = 0; i < instsLen; i++) {
			boolean inst = (insts & 0x01) == 0x01;
			insts >>>= 1;
			if (inst) {
				// push
				Entry in = input.removeFirst();
				List<Entry> list = new ArrayList<Entry>();
				list.add(in);
				list.add(in.negative());
				stack.push(list);
			} else {
				// pop
				if (stack.size() < 2) {
					// popできないので空のリストを返す
					return new ArrayList<Entry>();
				}
				List<Entry> rh = stack.pop();
				List<Entry> lh = stack.pop();
				List<Entry> popResult = new ArrayList<Entry>();
				for (Entry re : rh) {
					for (Entry le : lh) {
						popResult.add(le.add(re));
						popResult.add(le.sub(re));
						popResult.add(le.mul(re));
						popResult.add(le.div(re));
					}
				}
				stack.push(popResult);
			}
		}
		return stack.pop();
	}

	/**
	 * 数字のあらゆる連結方法を試す。
	 * @param digits 0..9の列
	 */
	private static void tryNumbers(List<Integer> digits) {
		List<Entry> result = new ArrayList<Entry>();

		// (桁数-1)のビット列を全て生成(0:分ける 1:連結する)
		int patternLen = digits.size() - 1;
		for (int pat = 0; pat < (1 << patternLen); pat++) {
			List<Entry> nums = new ArrayList<Entry>();
			nums.add(new Entry(digits.get(0)));
			for (int i = 1; i < digits.size(); i++) {
				if ((pat >>> (i - 1) & 0x1) == 0) {
					nums.add(new Entry(digits.get(i)));
				} else {
					Entry last = nums.remove(nums.size() - 1);
					nums.add(last.connect(new Entry(digits.get(i))));
				}
			}

			// 2N-1(push N回、pop N回)のビット列
			int instsLen = nums.size() * 2 - 1;
			for (int i = 0; i < (1 << instsLen) - 1; i++) {
				if (count1(i) == nums.size()) {
					result.addAll(processInsts(nums, i));
				}
			}
		}

		// for (Entry e : result) {
		// System.out.println(e);
		// }
		System.out.printf("All Expressions Count: %d%n", result.size());

		for (int i = PRINT_MIN; i <= PRINT_MAX; i++) {
			int find = 0;
			String example = null;
			for (Entry e : result) {
				if (Math.abs(e.result - i) < 1e-10) {
					find++;
					if (example == null) {
						example = e.expr;
					}
				}
			}
			if (example == null) {
				System.out.printf("%4d = (Impossible)%n", i);
			} else {
				System.out.printf("%4d = %s [%d patterns]%n", i, example, find);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		System.out.println("Digit count: ");
		int count = in.nextInt();
		System.out.println(count);
		List<Integer> digits = new ArrayList<Integer>();
		System.out.println("Digit data(ex. 2 0 1 0): ");
		for (int i = 0; i < count; i++) {
			int digit = in.nextInt();
			System.out.println(digit);
			if (digit < 0 || digit > 9)
				throw new RuntimeException("Digit must be 0<=d<=9.");
			digits.add(digit);
		}
		tryNumbers(digits);
	}

}