Columbus's bargain (UVa Live Archive Asia - 2009 Ningbo)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=353&page=show_problem&problem=2762

問題

ある金額kの商品は以下のルールで交換できる。

• k-1毎の金貨を支払う
• 同じ額の商品と交換する
• 別の商品+ある一定枚数のコインと交換する(別に与えられる)

各商品をいくらで買えるか答えよ。
0<商品の個数<=20
0<商品の金額<=30
0<交換の法則<=20

解法

てきとうにグラフを作って、ワーシャルフロイドする。