AtCoder AGC 019 A - Ice Tea Store (茶色, 300 点)

丁寧に簡潔に

問題へのリンク

問題概要

合計で グラム買いたい。

• 0.25 グラフで 円のセット
• 0.5 グラムで 円のセット
• 1 グラムで 円のセット
• 2 グラムで 円のセット

がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。

考えたこと

0.25 と 0.5 を両方使う意味はない。なぜなら、

• 2A < B なら、0.25 のみを使うのがよい
• 2A > B なら、0.5 のみを使うのがよい

からだ。同様にして、0.25, 0.5, 1 はいずれか1種類のみでよい。このことから、

• 1 グラムで min(4A, 2B, C) 円のセット
• 2 グラムで D 円のセット

を組み合わせようという問題になる。ここから先も「極端な場合」のみを考えれば良い。すなわち

• 全部 1 グラムだけ
• 2 グラムだけで買えるだけ買って、余ったぶんを 1 グラムで

のどちらかが最適解となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long Q, H, S, D, N;
    cin >> Q >> H >> S >> D >> N;
    long long one = min({Q*4, H*2, S});
    cout << min(one*N, D*(N/2)+one*(N%2)) << endl;
}