C - Sugar Water - AtCoder Regular Contest 083
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型ではなく、整数型で全部決定できるのでできればその方針で行う。