賢いお買い物 [yukicoder No.825]

https://yukicoder.me/problems/no/825

解説

https://yukicoder.me/submissions/345142

不確定な要素を全て全探索しよう。
不確定な要素は「商品の金額」「使った1G硬貨枚数」「使った10G硬貨枚数」であり、
これを全て全探索してもTLEせずに間に合う。
お釣りは合計枚数が最小な構成で帰ってくるとあるが、なるべく10G硬貨で帰ってくる構成が最小構成。

int A, B, C;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> A >> B >> C;
	int tot = A + B * 10;

	rep(item, 1, tot + 1) rep(a, 0, A + 1) rep(b, 0, B + 1) {
		int pay = a + b * 10;
		int change = pay - item;
		if (change < 0) continue;

		int rest = change / 10 + change % 10 + A - a + B - b;
		if (rest == C) {
			cout << item << endl;
			return;
		}
	}

	cout << "Impossible" << endl;
}