CodeIQの「目指せお釣りマスター！」 オリジナル問題は http://pavlocat.hatenadiary.jp/entry/2013/08/25/181515

answer.txt

4 1 0 0 0 0 0 0
0 0 0 1 0 0 1 1
7 0 0 0 1 1 0 0
9 0 0 1 0 0 0 0
2 0 0 1 0 2 0 1
1 0 0 0 1 0 0 1
8 0 1 0 0 0 0 0
5 0 0 0 1 2 1 1
3 0 0 1 0 0 0 0
6 0 0 1 0 0 0 0

27分
====使用言語=====
Java
====方針====
総当り。
一つ目の商品を選び、次に2つ目の商品と支払額を選び、、、というのを10個目まで続ける。
ただし、状態として「既にレジを通った商品および手元のお金の種類と数」が同じ場合は
最も経過時間の短いデータのみを有効とします。
たとえば、
0->1->2 手元に(0 0 1 0 2 0 1) 13分
0->1->2 手元に(0 0 1 0 2 0 1) 16分
0->2->1 手元に(0 0 1 0 2 0 1) 14分
とあった場合は一番上のデータのみ残って残りは破棄します。
※レジの順序が同じ場合でも支払いに使うお金の種類と数によって複数のパターンが生じます。

これでも時間をかければ何とか解けますが、より枝分かれを防ぐために次のように考えました。
「途中で1円玉が5枚以上になったり5円玉が2枚以上になるパターンが他のパターンよりも優れることはない」
例えば、10円玉1枚と5円玉2枚となるパターンがあったとしてそのパターン（A）は
同じ商品と順番で10円玉2枚と5円玉0枚となるパターン（B）と同等かより時間がかかるということです。
今回は答えをひとつ見つければいいのでAのようなパターンは破棄することにしました。

data.in.txt

56
46
71
93
84
76
98
58
129
80

data100.in.txt

78
295
51
45
74
176
143
24
98
120
23
26
162
207
15
27
170
138
72
179
58
155
42
12
39
76
89
54
97
84
127
378
66
55
51
58
292
100
141
45
65
208
15
243
218
28
71
192
55
20
65
82
43
51
76
89
44
47
66
100
136
70
144
61
37
63
61
69
27
67
135
222
102
380
45
28
36
118
153
8
112
192
50
33
349
3
7
48
52
87
97
47
83
115
167
138
102
186
76
39

OtsuriMaster.java

package matsuri2013;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

import org.apache.commons.io.FileUtils;

public class OtsuriMaster {

	private static Integer[] itemPrices;
	private static NodeSet nodeSet = new NodeSet();
	private static int threthold = 100000;
	private static int count = 0;

	public static void main(String[] args) throws IOException {
		long start = System.currentTimeMillis();
		List<String> lines = FileUtils.readLines(new File("D://dev/codeiq/q477_otsuri_master/data.in.txt"));
		itemPrices = new Integer[lines.size()];
		for (int index = 0; index < lines.size(); index++) {
			itemPrices[index] = Integer.parseInt(lines.get(index));
		}

		for (int index = 0; index < itemPrices.length; index++) {
			Node node = new Node(null, index, PriceDetail.get(1000));
			nodeSet.add(node);
		}

		while (nodeSet.nodes.size() != 0) {
			List<Node> nodes = new ArrayList<OtsuriMaster.Node>();
			nodes.addAll(nodeSet.nodes);
			Collections.sort(nodes);
			nodeSet = new NodeSet();
			for (Node node : nodes) {
				if (node.totalMinute > threthold) {
					continue;
				}
				count++;
				calcChildren(node);
			}
		}

		System.out.println("count:" + count);
		Collections.sort(nodeSet.results);
		for (Node result : nodeSet.results) {
			result.printResult();
			System.out.println("===============");
		}
		long end = System.currentTimeMillis();
		System.out.println((end - start) + "msec");
	}

	public static void calcChildren(Node node) {
		for (int index = 0; index < itemPrices.length; index++) {
			if (!node.paid.contains(index)) {
				Integer price = itemPrices[index];
				for (PriceDetail detail : node.wallet.candidates()) {
					if (detail.price() >= price) {
						Node child = new Node(node, index, detail);
						nodeSet.add(child);
					}
				}
			}
		}
	}

	public static PriceDetail subtract(PriceDetail wallet, PriceDetail payment) {
		Map<Money, Integer> map = new HashMap<OtsuriMaster.Money, Integer>();
		for (Money money : Money.values()) {
			int count = wallet.count(money) - payment.count(money);
			map.put(money, count);
			if (count < 0) {
				throw new IllegalStateException(money.name() + ":" + count);
			}
		}
		return PriceDetail.get(map);
	}

	public static PriceDetail add(PriceDetail wallet, PriceDetail returned) {
		Map<Money, Integer> map = new HashMap<OtsuriMaster.Money, Integer>();
		for (Money money : Money.values()) {
			int count = wallet.count(money) + returned.count(money);
			map.put(money, count);
		}
		return PriceDetail.get(map);
	}

	public static PriceDetail pay(int price, PriceDetail payment) {
		int back = payment.price() - price;
		if (back < 0) {
			throw new IllegalArgumentException("price=" + price + ", payment=" + payment.price());
		}
		return PriceDetail.get(back);
	}

	public static List<PriceDetail> paymentCandidates(PriceDetail wallet, int price) {
		List<PriceDetail> details = new ArrayList<OtsuriMaster.PriceDetail>();
		for (PriceDetail detail : wallet.candidates()) {
			if (detail.price() >= price) {
				details.add(detail);
			}
		}
		return details;
	}

	public static class NodeSet {
		private List<Node> nodes = new ArrayList<OtsuriMaster.Node>();
		private Map<String, Node> nodeMap = new HashMap<String, OtsuriMaster.Node>();
		private List<Node> results = new ArrayList<OtsuriMaster.Node>();

		public void add(Node node) {
			if (node.wallet.warning() || node.payment.warning()) {
				return;
			}
			if (node.totalMinute > threthold) {
				return;
			}
			if (node.paid.size() == itemPrices.length) {
				if (results.size() > 0 && results.get(0).totalMinute > node.totalMinute) {
					results.clear();
				}
				results.add(node);
				if (threthold > node.totalMinute) {
					threthold = node.totalMinute;
				}
				return;
			}
			String key = node.stateKey();
			if (nodeMap.containsKey(key)) {
				Node inMap = nodeMap.get(key);
				if (inMap.totalMinute == node.totalMinute) {
					//TODO: 
				} else if (inMap.totalMinute > node.totalMinute) {
					nodeMap.put(key, node);
					nodes.add(node);
					nodes.remove(inMap);
				}
			} else {
				nodeMap.put(key, node);
				nodes.add(node);
			}
		}
	}

	public static class Node implements Comparable<Node> {
		private Set<Integer> paid = new TreeSet<Integer>();
		private int index;
		private PriceDetail payment;
		private PriceDetail wallet;
		private int minute = 0;
		private List<Node> parentNodes = new ArrayList<OtsuriMaster.Node>();
		private int totalMinute = 0;

		public Node(Node parent, int index, PriceDetail payment) {
			if (parent != null) {
				this.paid.addAll(parent.paid);
			}
			this.paid.add(index);
			this.index = index;
			this.payment = payment;

			PriceDetail returned = pay(itemPrices[index], payment);
			if (parent != null) {
				this.wallet = subtract(parent.wallet, payment);
				this.wallet = add(wallet, returned);
			} else {
				this.wallet = returned;
			}
			this.minute = returned.count();
			if (parent != null) {
				this.parentNodes.addAll(parent.parentNodes);
				this.parentNodes.add(parent);
				this.totalMinute += parent.totalMinute;
			}
			this.totalMinute += this.minute;
		}

		public String stateKey() {
			StringBuilder str = new StringBuilder();
			for (Integer num : paid) {
				str.append(num).append(",");
			}
			str.append(":");
			str.append(wallet.value());
			return str.toString();
		}

		public void printResult() {
			for (Node path : parentNodes) {
				System.out.println(path.result());
			}
			System.out.println(this.result());
		}

		private String result() {
			StringBuilder str = new StringBuilder();
			str.append(this.index).append(" ").append(this.payment.value());
			return str.toString();
		}

		private String path() {
			StringBuilder str = new StringBuilder();
			for (Node path : parentNodes) {
				str.append(path.index);
				str.append(" ");
			}
			str.append(this.index);
			return str.toString();
		}

		@Override
		public int compareTo(Node o) {
			int tmp1 = this.totalMinute - o.totalMinute;//小さいほうがいい
			if (tmp1 != 0) {
				return tmp1;
			}
			return this.path().compareTo(o.path());
		}
	}

	public static class PriceDetail {
		private int[] countMoney = new int[Money.values().length];
		private static Map<String, PriceDetail> factoryMap = new HashMap<String, OtsuriMaster.PriceDetail>();

		public static PriceDetail get(Map<Money, Integer> map) {
			String key = key(map);
			if (factoryMap.containsKey(key)) {
				return factoryMap.get(key);
			}
			PriceDetail detail = new PriceDetail(map.get(Money.P1000), map.get(Money.C500), map.get(Money.C100)
				, map.get(Money.C50), map.get(Money.C10), map.get(Money.C5), map.get(Money.C1));
			factoryMap.put(key, detail);
			return detail;
		}

		public static PriceDetail get(int price) {
			Map<Money, Integer> map = new HashMap<OtsuriMaster.Money, Integer>();
			int remain = price;
			for (Money money : Money.values()) {
				if (remain >= money.price) {
					int count = remain / money.price;
					map.put(money, count);
					remain -= count * money.price;
				} else {
					map.put(money, 0);
				}
			}
			return get(map);
		}

		private PriceDetail(int count1000, int count500, int count100
				, int count50, int count10, int count5, int count1) {
			this.countMoney[Money.P1000.ordinal()] = count1000;
			this.countMoney[Money.C500.ordinal()] = count500;
			this.countMoney[Money.C100.ordinal()] = count100;
			this.countMoney[Money.C50.ordinal()] = count50;
			this.countMoney[Money.C10.ordinal()] = count10;
			this.countMoney[Money.C5.ordinal()] = count5;
			this.countMoney[Money.C1.ordinal()] = count1;
		}

		public boolean warning() {
			if (this.count(Money.P1000) >= 2 
					|| this.count(Money.C500) >= 2 || this.count(Money.C100) >= 5
					|| this.count(Money.C50) >= 2 || this.count(Money.C10) >= 5
					|| this.count(Money.C5) >= 2 || this.count(Money.C1) >= 5) {
				return true;
			}
			return false;
		}

		public int count(Money money) {
			return this.countMoney[money.ordinal()];
		}
		public int price(Money money) {
			return this.countMoney[money.ordinal()] * money.price;
		}
		
		public int price() {
			int price = 0;
			for (Money money : Money.values()) {
				price += price(money);
			}
			return price;
		}

		public int count() {
			int count = 0;
			for (Money money : Money.values()) {
				count += count(money);
			}
			return count;
		}

		private List<PriceDetail> candidates;
 		public List<PriceDetail> candidates() {
 			if (candidates == null) {
 				candidates = candidates(Money.P1000, new HashMap<OtsuriMaster.Money, Integer>());
 			}
			return candidates;
		}

 		private List<PriceDetail> candidates(Money money, Map<Money, Integer> partialMap) {
 			List<PriceDetail> details = new ArrayList<OtsuriMaster.PriceDetail>();
 			int ord = money.ordinal();
 			
 			int count = count(money);
 			for (int num = 0; num <= count; num++) {
 				Map<Money, Integer> map = new HashMap<OtsuriMaster.Money, Integer>();
 				for (Money m : Money.values()) {
 					if (m.ordinal() < money.ordinal()) {
 						map.put(m, partialMap.get(m));
 					}
 				}
 				map.put(money, num);
 				if (ord + 1 < Money.values().length) {
 		 			Money next = Money.values()[ord + 1];
 	 				details.addAll(candidates(next, map));
 				} else {
 	 				PriceDetail detail = PriceDetail.get(map);
 	 				if (!detail.warning()) {
 	 	 				details.add(detail);
 	 				}
 				}
 			}
 			return details;
 		}

 		public static String key(Map<Money, Integer> map) {
			StringBuilder str = new StringBuilder();
			String separator = "";
			for (Money money : Money.values()) {
				if (map.containsKey(money)) {
					str.append(separator);
					str.append(map.get(money));
					separator = " ";
				}
			}
			return str.toString();
		}

 		public String value() {
 			Map<Money, Integer> map = new HashMap<OtsuriMaster.Money, Integer>();
 			for (Money money : Money.values()) {
 				map.put(money, count(money));
 			}
			return key(map);
		}
	}

	public static enum Money {
//		P10000(10000),
//		P5000(5000),
		P1000(1000),
		C500(500),
		C100(100),
		C50(50),
		C10(10),
		C5(5),
		C1(1),
		;
		
		public int price;
		Money(int price) {
			this.price = price;
		}
	}
}