C - Sugar Water - AtCoder Regular Contest 083

C - Sugar Water

A, B, C, D, E, Fが与えられる。空のビーカーに次の操作のいずれかを何回でも行える。

• 100A[g]の水追加
• 100B[g]の水追加
• C[g]の砂糖追加
• D[g]の砂糖追加

現在水100[g]当たりE[g]砂糖が溶け、ビーカーには最大F[g]の砂糖+水が入るとすると、最大濃度のときの砂糖水と砂糖の重量を答えよ。(答えはいくつかある)

A, B, C, Dの操作を行い、メモ化再帰で容量Fに到達するまで全探索する。それぞれの制限が小さいからといってメモ化をサボるとTLEになるので注意。メモ化のキーは現在の{水の量, 砂糖の量}など。double型ではなく、整数型で全部決定できるのでできればその方針で行う。