AGC019 A - Ice Tea Store

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    Q, H, S, D = il()
    N = ii()
    h = min(Q * 4, H * 2, S)

    if h * 2 < D:
        print(h * N)
    else:
        d, m = divmod(N, 2)
        print(D * d + h * m)


if __name__ == '__main__':
    main()

考え方

どのような買い方が発生しうるかを考えます。
購入する量のNは1 <= N <= 10 ** 9の範囲です。
最低でも1で、小数点以下は発生しません。
つまり、0.25リットルは４つから0.5リットルは２つからの購入となります。

以上から1リットルだけ購入するときの最小金額はmin( Q * 4, H * 2, S)となります。

あとは1リットルの最低金額と2リットルの金額Dから、
効率的な買い方を考えます。

1リットルの最低金額が、D // 2以下の場合には、
1リットルの最低金額 * Nが回答となります。
1リットルの最低金額が、D // 2以上の場合には、
Dで買えるだけ買ったあと、余りを1リットルの最低金額で購入した値段が最も安い金額となります。