Problem:


Discounts of Buckwheat

Aizu is famous for its buckwheat. There are many people who make buckwheat noodles by themselves.

  One day, you went shopping to buy buckwheat flour. You can visit three shops, A, B and C. The amount in a bag and its unit price for each shop is determined by the follows table. Note that it is discounted when you buy buckwheat flour in several bags.

             Shop A     Shop B     Shop C

  Amount in a bag    200g   300g   500g

 Unit price for a bag (nominal cost) 380 yen   550 yen   850 yen

 Discounted units  per 5 bags per 4 bags per 3 bags

 Discount rate   reduced by 20 %  reduced by 15 %  reduced by 12 %

 For example, when you buy 12 bags of flour at shop A, the price is reduced by 20 % for 10 bags, but not for other 2 bags. So, the total amount shall be (380 &times; 10) &times; 0.8 + 380 &times; 2 = 3,800 yen.

  Write a program which reads the amount of flour, and prints the lowest cost to buy them. Note that you should buy the flour of exactly the same amount as the given input.

Input

  The input consists of multiple datasets. For each dataset, an integer a (500 ≤ a ≤ 5000, a is divisible by 100) which represents the amount of flour is given in a line.

  The input ends with a line including a zero. Your program should not process for the terminal symbol. The number of datasets does not exceed 50.

Output

  For each dataset, print an integer which represents the lowest cost.

Sample Input

500
2200
0

Output for the Sample Input

850
3390



Sample input:
500
2200
0


Sample output:
850
3390

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


while True:

    N = int(input()) #量
    if N == 0:
        break

    ans = BIG_NUM

    lim_A = N//200
    lim_B = N//300
    lim_C = N//500

    for a in range(lim_A+1):
        for b in range(lim_B+1):
            if 200*a+300*b > N:
                break
            rest = N-(200*a+300*b)
            if rest%500 != 0:
                continue
            c = rest//500

            sum_A = 380*(a%5)+304*(a-(a%5))
            sum_B = 550*(b%4)+935*(b-(b%4))//2
            sum_C = 850*(c%3)+1496*(c-(c%3))//2

            ans = min(ans,sum_A+sum_B+sum_C)

    print("%d"%(ans))

Submission status: Accepted

Solution code:
# coding=utf-8

###
### for python program
###

import sys
import math

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    def pnum_check(self, n):
        if (n==1):
            return False
        elif (n==2):
            return True
        else:
            for x in range(2,n):
                if(n % x==0):
                    return False
            return True

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]

#R = float(input())
#A.append(list(map(int,input().split())))

#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

#abc list
#abc = [chr(ord('a') + i) for i in range(26)]

### output sample
# print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
# print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
# print(" {}".format(i), end="")

def printA(A):
    N = len(A)
    for i, n in enumerate(A):
        print(n, end='')
        if i != N-1:
            print(' ', end='')
    print()

# リスト内包表記 ifあり
# [x-k if x != 0 else x for x in C]

# ソート
# N = N.sort()

# 10000個の素数リスト
# P = mymath.pnum_eratosthenes(105000)

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

def dist(A, B):
    d = 0
    for i in range(len(A)):
        d += (A[i]-B[i])**2            
    d = d**(1/2)
    return d

def get_input():
    N = []
    while True:
        try:
            N.append(input())
            #N.append(int(input()))
            #N.append(float(input()))
        except EOFError:
            break
    return N

while True:
    M = int(input())
    if M==0:
        break
    
    cost = 1145141919

    for x1 in range(M//200+1):
        M1 = M - 200 * x1
        for x2 in range(M1//300+1):
            M2 = M1 - 300 * x2
            for x3 in range(M2//500+1):
                M3 = M2 - 500 * x3
                if M3 == 0:
                    f = 380*(x1%5) + 304*5*(x1//5) + 550*(x2%4) + 467.5*4*(x2//4) + 850*(x3%3) + 748*3*(x3//3)
                    if cost > f:
                        cost = f
                        #print(x1,x2,x3,f)

    print(int(cost))

Submission status: Accepted

Solution code:
while 1:
    try:
        inp=int(input())
        if inp==0:break
        m_list=[]
        for i in range(4):
            for j in range(5):
                for k in range(6):
                    for l in range(3):
                        for m in range(4):
                            for n in range(5):
                                if i*1500+j*1200+k*1000+l*500+m*300+n*200==inp:
                                    m_list.append(i*2244+j*1870+k*1520+l*850+m*550+n*380)
        print(min(m_list))
    except:break

Submission status: Accepted

Solution code:
while True:
    g = int(input())//100
    if g == 0:
        break
    p = 100000
    for a in range(g//2 + 1):
        for b in range(g//3 + 1):
            for c in range(g//5 + 1):
                if a*2 + b*3 + c*5 == g:
                    p = min(p, 1520*(a//5) + 380*(a%5) + 1870*(b//4) + 550*(b%4) + 2244*(c//3) + 850*(c%3))
    print(p)

Submission status: Accepted

Solution code:
INF = 10**20
def solve(n):
    inf = INF
    for i in range((n//500) + 1):
        for j in range(((n - 500*i)//300) + 1):
            if ((n - 500*i - 300*j)%200 == 0):
                a = (n - 500*i - 300*j)//200
                va = (a//5)*380*5*0.8 + (a%5)*380
                vj = (j//4)*550*4*0.85 + (j%4)*550
                vi = (i//3)*850*3*0.88 + (i%3)*850
                inf = min(inf, va+vj+vi)
    print(int(inf))
            
while True:
    n = int(input())
    if (not n):
        break
    solve(n)

Submission status: Accepted

Solution code:
p1,p2,p3 = 380,550,850
q1,q2,q3 = 200,300,500
d1,d2,d3 = 5,4,3
r1,r2,r3 = 0.2,0.15,0.12
arr = []
for tot in range(500,5001,100):
    lst = 1000000000
    for i in range(0,int(tot/q1)+1):
        for j in range(0,int(tot/q2)+1):
            for k in range(0,int(tot/q3)+1):
                if i*q1+j*q2+k*q3 == tot:
                    tmp = i*p1+j*p2+k*p3 - int(i/d1)*d1*p1*r1 - int(j/d2)*d2*p2*r2 - int(k/d3)*d3*p3*r3
                    lst = min(tmp,lst)
    arr.append([tot,int(lst)])
dic = dict(arr)
while(True):
    n = int(input())
    if n == 0:
        break
    print(dic[n])

Submission status: Runtime Error

Solution code:
def solve2(amount):
    """
    ???????¨???????????????¨?????????????????§???
    """
    packages = [(0, 0), (2, 380), (3, 550), (5, 850), (10, 1520), (12, 1870), (15, 2244)] # 1?¢??????????(100g??????)??¨??????????????¢l
    # dp??¨???2?¬??????????????¨?????????????(100g??????)?????????????????¨??§??????packages????¨????
    # 999999...??????INF??¨?????? (phthon 3.5??\??????????????????math.inf????????¨??§??????)
    cart = [[99999999] * (amount//100 + 1) for _ in range(len(packages))]
    for i in range(len(packages)):
        cart[i][0] = 0          #  0g???????????\????????´??????0???????????????

    for i in range(1, len(packages)):
        for j in range(1, len(cart[0])):
            w = packages[i][0]  #  ??????
            p = packages[i][1]  #  ??????
            # ???????????????????????????????????????????????????????????????????????????????¨????
            cart[i][j] = min(cart[i-1][j], cart[i-1][max(0, j-w)]+p, cart[i][max(0, j-w)]+p)
    return cart[-1][-1]


def main(args):
    while True:
        amount = int(input())
        if amount == 0:
            break
        result = solve2(amount)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])