けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

丁寧に簡潔に

問題へのリンク

問題概要

合計で  N グラム買いたい。

  • 0.25 グラフで  A 円のセット
  • 0.5 グラムで  B 円のセット
  • 1 グラムで  C 円のセット
  • 2 グラムで  D 円のセット

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

考えたこと

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;
}