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: Wrong Answer

Solution code:
while True:
    n = int(input())
    if n==0:
        break
    if n % 200 == 0:
        a = n / 200
    else :
        a = n / 200 + 1
    a = (380 * (a - a % 5)) * 0.8 + 380 * (a % 5)
    if n % 300 == 0:
        b = n / 300
    else :
        b = n / 300 + 1
    b = (550 * (b - b % 4)) * 0.85 + 550 * (b % 4)
    if n % 500 == 0:
        c = n / 500
    else :
        c = n / 500 + 1
    c = (850 * (c - c % 3)) * 0.88 + 850 * (c % 3)

    if a < b:
        if a < c:
            #print ('a')
            print (int(a))
        else :
            #print ('c')
            print (int(c))
    elif b < c:
        #print ('b')
        print (int(b))
    else :
        #print ('c')
        print (int(c))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0106&lang=jp
"""
import sys


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 solve(amount):
    """
    :param amount: ?????\???????????°?????????
    :return: ?????????
    """
    best_price = (amount + 199) // 200 * 380
    for a in range(amount // 200 + 1):
        for b in range(amount // 300 + 1):
            for c in range(amount // 500 + 1):
                for a1 in range(amount // 1000 + 1):
                    for b1 in range(amount // 1200 + 1):
                        for c1 in range(amount // 1500 + 1):
                            if a*200 + b*300 + c*500 + a1*1000 + b1*1200 + c1*1500 == amount:
                                price = a*380 + b*550 + c*850 + a1*1520 + b1*1870 + c1*2244
                                if price < best_price:
                                    best_price = price
    return best_price


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


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

Submission status: Wrong Answer

Solution code:
def dis(price, n, c, rate):
  d = (n / c) * c
  return price * (n - d) + price * d * rate

def gram(a, b, c):
  return 200 * a + 300 * b + 500 * c

def calc(a, b, c):
  return dis(380, a, 5, 0.8) + dis(550, b, 4, 0.85) + dis(850, c, 3, 0.88)

while True:
  f = input()
  if f == 0:
    break
  ans = []
  a, b, c = 1, 1, 1

  for a in range(f / 200 + 1):
    for b in range(f / 300 + 1):
      for c in range(f / 500 + 1):
        if gram(a, b, c) <= f + 500:
          ans.append([gram(a, b, c), calc(a, b, c)])
  
  for n in sorted(ans, key = lambda x: x[1]):
    if n[0] >= f:
      print int(n[1])
      break

Submission status: Wrong Answer

Solution code:
def dis(price, n, c, rate):
  d = (n / c) * c
  return price * (n - d) + price * d * rate

def gram(a, b, c):
  return 200 * a + 300 * b + 500 * c

def calc(a, b, c):
  return dis(380, a, 5, 0.8) + dis(550, b, 4, 0.85) + dis(850, c, 3, 0.88)

ans = []
for a in range(25):
  for b in range(17):
    for c in range(10):
      if gram(a, b, c) < 5500:
        ans.append([gram(a, b, c), calc(a, b, c)])

while True:
  f = input()
  if f == 0:
    break
  for n in sorted(ans, key = lambda x: x[1]):
    if n[0] >= f:
      print int(n[1])
      break

Submission status: Wrong Answer

Solution code:
def ceil(n, m):
  return n / m + 2 if n % m != 0 else n / m + 1

def gram(l):
  return 200 * l[0] + 300 * l[1] + 500 * l[2]

def price(l):
  def c(n, m, p, r):
    d = (n / m) * m
    return ((n - d) + d * r) * p

  return int(c(l[0], 5, 380, 0.80) + c(l[1], 4, 550, 0.85) + c(l[2], 3, 850, 0.88))

t = []
for amount in range(500, 5500, 100):
  for a in range(ceil(amount, 200)):
    for b in range(ceil(amount, 300)):
      for c in range(ceil(amount, 500)):
        if gram([a, b, c]) == amount:
          t.append([gram([a, b, c]), [a, b, c]])

while True:
  data = input()
  if data == 0:
    break
  s = []
  for x in t:
    if x[0] >= data and x[0] < data + 500:
      s.append(price(x[1]))
  print sorted(s)[0]

Submission status: Wrong Answer

Solution code:
w=[200,300,500,1000,1200,1500]
p=[380,550,850,1520,1870,2244]
s=[0]*5001
for i in xrange(100,5001,100):
    s[i]=min([p[j]+s[i-w[j] if i-w[j]>=0 else 0] for j in xrange(6)])
while True:
    n=input()
    if n==0:
        break
    print s[n]

Submission status: Wrong Answer

Solution code:
w=[200,300,500,1000,1200,1500]
p=[380,550,850,1520,1870,2244]
dp=[2<<20]*5001
dp[0]=0
for k in xrange(6):
    for i in xrange(0,5000-w[k],100):
        dp[i+w[k]] = min(dp[i+w[k]] , dp[i]+p[k])
while True:
    n=input()
    if n==0:
        break
    print dp[n]

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    table = (0, 0, 330, 550, 760, 850, 1100, 1230, 1400, 1610, 1520,
             1950, 1870, 2070, 2250, 2370, 2620, 2720, 2920, 3100, 3040,
             3470, 3390, 3590, 3740, 3890, 4140, 4240, 4440, 4590, 4560,
             4990, 4910, 5110, 5260, 5410, 5660, 5760, 5960, 6110, 6080,
             6510, 6430, 6630, 6780, 6930, 7180, 7280, 7480, 7630, 7600)
    while 1:
        weight = int(readline())
        if not weight:
            exit()
        print(table[weight//100])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    table = (0, 0, 380, 550, 760, 850, 1100, 1230, 1400, 1610, 1520,
             1950, 1870, 2070, 2250, 2370, 2620, 2720, 2920, 3100, 3040,
             3470, 3390, 3590, 3740, 3890, 4140, 4240, 4440, 4590, 4560,
             4990, 4910, 5110, 5260, 5410, 5660, 5760, 5960, 6110, 6080,
             6510, 6430, 6630, 6780, 6930, 7180, 7280, 7480, 7630, 7600)
    while 1:
        weight = int(readline())
        if not weight:
            exit()
        print(table[weight//100])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
r = 5001
wc = [[1500,2244],[1000,1520],[1200,1870],[500,850],[300,550],[200,380]]
dp = [0]*r
for w,c in wc:
	i = 1
	while w * i < 5001:
		if dp[w * i] == 0:
			dp[w * i] = c * i
		i += 1
	for i in range(5001 - w):
		if dp[i] > 0 and dp[i + w] == 0:
			dp[i + w] = dp[i] + c

while 1:
	n = input()
	if n == 0: break
	print dp[n]

Submission status: Wrong Answer

Solution code:
r = 5001
wc = [[1500,2244],[1000,1520],[1200,1870],[500,850],[300,550],[200,380]]
dp = [0]*r
for w,c in wc:
	dp[w] = c
	for i in range(r - w):
		if dp[i] > 0 and dp[i + w] == 0:
			dp[i + w] = dp[i] + c

while 1:
	n = input()
	if n == 0: break
	print dp[n]

Submission status: Wrong Answer

Solution code:
r = 5001
wc = [[1500,2244],[1000,1520],[1200,1870],[500,850],[300,550],[200,380]]
dp = [0]*r
for w,c in wc:
	dp[w] = c
	for i in range(r - w + 1):
		if dp[i] > 0 and dp[i + w] == 0:
			dp[i + w] = dp[i] + c

while 1:
	n = input()
	if n == 0: break
	print dp[n]

Submission status: Wrong Answer

Solution code:
r = 51
wc = [[15,2244],[10,1520],[12,1870],[5,850],[3,550],[2,380]]
dp = [0]*r
for w,c in wc:
	dp[w] = c
	for i in range(2,r - w):
		if dp[i] > 0 and dp[i + w] == 0:
			dp[i + w] = dp[i] + c

while 1:
	n = input()
	if n == 0: break
	print dp[n/100]

Submission status: Wrong Answer

Solution code:
r = 51
wc = [[15,2244],[12,1870],[10,1520],[5,850],[3,550],[2,380]]
dp = [0]*r
for w,c in wc:
	dp[w] = c
	for i in range(r - w):
		if dp[i] > 0 and dp[i + w] == 0:
			dp[i + w] = dp[i] + c

while 1:
	n = input()
	if n == 0: break
	print dp[n/100]

Submission status: Time Limit Exceeded

Solution code:
def sensation():
    global total
    for k in keys:
        if (total + k) < g:
            splash.append(k)
            total += k
            sensation()
            del splash[-1]
            total -= k
        elif (total + k) == g:
            splash.append(k)
            ridiculous_thing()
            del splash[-1]
        
def ridiculous_thing():
    a_m = 0
    if not sorted(splash) in lego:
        lego.append(sorted(splash))
        for s in splash:
            a_m += heritage[s]
        else:
            result.append(a_m)

heritage = {200:380, 300:550, 500:850, 1000:1520, 1200:1870, 1500:2244}

while True:
    g = int(raw_input())
    if g == 0: break
    keys = sorted(heritage.keys(), reverse=True)
    total = 0
    splash = []
    result = []
    lego = []
    sensation()
    result.sort()
    print result[0]

Submission status: Time Limit Exceeded

Solution code:
while True:
	amount = int(input())
	decide = [0,0,0,0,0,0]
	unit = [200,300,500,1000,1200,1500]
	m_unit = [320,550,850,1520,1870,2244]
	n = amount
	res = 0
	if n == 0:
		break
	while n != 0:
		for i in [5,4,3,2,1,0]:
			if n >= unit[i]:
				decide[i] += 1
				n -= unit[i]
			if n < 200:
				for j in [5,4,3,2,1,0]:
					if decide[j] != 0:
						decide = [0,0,0,0,0,0]
						decide[j-1] += 1
						n = amount-unit[j-1]
	for i in range(6):
		res += decide[i]*m_unit[i]
	print(res)

Submission status: Accepted

Solution code:
cost = {15:2244,12:1870,10:1520,5:850,3:550,2:380}

mincost =  [10000]*51

for j in cost:
    mincost[j] = cost[j]
for i in range(4,51):
    for j in cost:
        if mincost[i-j] < 10000 and mincost[i] > mincost[i-j] + cost[j]:
            mincost[i] = mincost[i-j] + cost[j]

while True:
    n = int(raw_input())
    if n == 0:
        break 
    print mincost[n/100]

Submission status: Accepted

Solution code:
def f(w1):
  x=[]
  a1=w1/500
  for i1 in range(a1+1):
    w2=w1-i1*500
    a2=w2/300
    for i2 in range(a2+1):
      w3=w2-i2*300
      if w3%200==0: x.append([w3/200,i2,i1])
  return x

def g(x):
  m=1e9
  A=[380,550,850]
  B=[.2,.15,.12]
  C=[5,4,3]
  for e in x:
    a=0
    for i in [0,1,2]:
      b=e[i]/C[i]*C[i]
      a+=A[i]*(e[i]-b*B[i])
    m=min(m,a)
  return m

while 1:
  w=input()
  if w==0: break
  print int(g(f(w)))

Submission status: Accepted

Solution code:
def f(w1):
  m=1e9
  for i1 in range(w1/500+1):
    w2=w1-i1*500
    for i2 in range(w2/300+1):
      w3=w2-i2*300
      if w3%200==0: m=min(m,g([w3/200,i2,i1]))
  return m

def g(x):
  A=[380,550,850]
  B=[.2,.15,.12]
  C=[5,4,3]
  return sum([A[i]*(x[i]-x[i]/C[i]*C[i]*B[i]) for i in [0,1,2]])

while 1:
  w=input()
  if w==0: break
  print int(f(w))

Submission status: Accepted

Solution code:
def f(w1):
  m=1e9
  for i1 in range(w1/5+1):
    w2=w1-i1*5
    for i2 in range(w2/3+1):
      w3=w2-i2*3
      if w3%2==0: m=min(m,g([w3/2,i2,i1]))
  return m

def g(x):
  A=[380,550,850]
  B=[.2,.15,.12]
  C=[5,4,3]
  return sum([A[i]*(x[i]-x[i]/C[i]*C[i]*B[i]) for i in [0,1,2]])

while 1:
  w=input()
  if w==0: break
  print int(f(w/100))

Submission status: Accepted

Solution code:
P=[99999,99999,380,550,760,850,1100,1230,1400,1610,1520,1950,1870,2070,2250,2244]
for i in range(16,51):
    P.append(min(P[i-2]+380,P[i-3]+550,P[i-5]+850,P[i-10]+1520,P[i-12]+1870,P[i-15]+2244))

while(1):
    q=int(raw_input())
    if q==0:
        break
    else:
        print P[q/100]

Submission status: Accepted

Solution code:
while True:
    N = int(input())
    if not N: break
    ans = float('inf')
    for c200 in range(N//200+1):
        for c300 in range(N//300+1):
            for c500 in range(N//500+1):
                if 200 * c200 + c300 * 300 + c500 * 500 == N:
                    ans = min(ans, 1520*(c200//5)+380*(c200%5)+1870*(c300//4)+550*(c300%4)+2244*(c500//3)+850*(c500%3))
    print(ans)

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  c = 10000
  for i in range(n//500+1):
    n1 = n - 500*i
    c1 = (850*3*0.88)*(i//3)+850*(i%3) 
    for j in range(n1//300+1):
      n2 = n1 - 300*j
      if n2 % 200 == 0:
        k = n2 // 200
        c2 = c1 + (550*4*0.85)*(j//4)+550*(j%4)+(380*5*0.8)*(k//5)+380*(k%5)
        if c2 <= c:
          c = c2
  print(int(c))

Submission status: Accepted

Solution code:
while True:
	n = int(input())
	if n == 0:
		break
	cheapest = float('inf')
	for bagsA in range(n // 200 + 1):
		for bagsB in range(n // 300 + 1):
			for bagsC in range(n // 500 + 1):
				if 200 * bagsA + 300 * bagsB + 500 * bagsC == n:
					price = 1520 * (bagsA // 5) + 380 * (bagsA % 5) + 1870 * (bagsB // 4) + 550 * (bagsB % 4) + 2244 * (bagsC // 3) + 850 * (bagsC % 3)
					cheapest = min(cheapest, price)
	print(cheapest)

Submission status: Accepted

Solution code:
a=[2,3,5,10,12,15]
b=[380,550,850,1520,1870,2244]
while 1:
    n=int(input())
    if n==0:break
    n//=100
    dp=[0]+[1<<29]*n
    for i in range(5,-1,-1):
        for j in range(n+1):
            if j+a[i]<=n and dp[j]!=1<<29:dp[j+a[i]]=min(dp[j+a[i]],dp[j]+b[i])
    print(dp[n])

Submission status: Accepted

Solution code:
a=[(2,380),(3,550),(5,850),(10,1520),(12,1870),(15,2244)]
dp=[1<<20]*51
for i,j in a:
    dp[i]=j
    for k in range(51-i):
        if dp[k]!=1<<20 and dp[k+i]>dp[k]+j:
            dp[k+i]=dp[k]+j
while 1:
    n=int(input())
    if n==0:break
    print(dp[n//100])

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
while True:
    price = int(input())
    if price == 0: break
    candidates = []
    for i in range(1, 25):
        tmp = list(combinations_with_replacement([200, 300, 500], i))
        for t in tmp:
            if sum(t) == price:
                candidates.append(t)
    ans = []
    for candidate in candidates:
        i=j=k=0
        for c in candidate:
            if c == 200:
                i += 1
            elif c == 300:
                j += 1
            else:
                k += 1
        m200, m300, m500 = divmod(i, 5)[1], divmod(j, 4)[1], divmod(k, 3)[1]
        ans.append(380*(i-m200)*0.8+380*m200 + 550*(j-m300)*0.85+550*m300 + 850*(k-m500)*0.88+850*m500)
    print(int(min(ans)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break

    costs = []
    for a in range(0, 26):
        for b in range(0, 17):
            for c in range(0, 11):
                # candidate
                if a * 200 + b * 300 + c * 500 == n:
                    cost = 0
                    a_bulk_num = a // 5
                    a_price_down_num = a_bulk_num * 5
                    a_normal_price_num = a - a_price_down_num
                    cost += 380 * 0.8 * a_price_down_num + 380 * a_normal_price_num

                    b_bulk_num = b // 4
                    b_price_down_num = b_bulk_num * 4
                    b_normal_price_num = b - b_price_down_num
                    cost += 550 * 0.85 * b_price_down_num + 550 * b_normal_price_num

                    c_bulk_num = c // 3
                    c_price_down_num = c_bulk_num * 3
                    c_normal_price_num = c - c_price_down_num
                    cost += 850 * 0.88 * c_price_down_num + 850 * c_normal_price_num

                    costs.append(cost)

    print(int(min(costs)))

Submission status: Accepted

Solution code:
Soba = [[2,380],[3,550],[5,850],[10,1520],[12,1870],[15,2244]] #???,??????
while True:
    g = int(input())
    if g == 0:
        break
    g_g = int(g / 100)
    DP = [[10000 for j in range(g_g + 1)] for i in range(7)]
    for i in range(7):
        DP[i][0] = 0
    for i in range(7):
        for j in range(g_g + 1):
            if j - Soba[i - 1][0] + 1 >= 0: 
                DP[i][j] = min(DP[i-1][j],DP[i][j - Soba[i - 1][0]] + Soba[i - 1][1])
            else:
                DP[i][j] = DP[i - 1][j]
    print(DP[6][g_g])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0106&lang=jp
"""
import sys


def solve(amount):
    """
    :param amount: ?????\???????????°?????????
    :return: ?????????
    """
    best_price = (amount + 199) // 200 * 380
    for a in range(amount // 200 + 1):
        for b in range(amount // 300 + 1):
            for c in range(amount // 500 + 1):
                for a1 in range(amount // 1000 + 1):
                    for b1 in range(amount // 1200 + 1):
                        for c1 in range(amount // 1500 + 1):
                            if a*200 + b*300 + c*500 + a1*1000 + b1*1200 + c1*1500 == amount:
                                price = a*380 + b*550 + c*850 + a1*1520 + b1*1870 + c1*2244
                                if price < best_price:
                                    best_price = price
    return best_price




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



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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0106&lang=jp
"""
import sys


def solve(amount):
    """
    :param amount: ?????\???????????°?????????
    :return: ?????????
    """
    best_price = (amount + 199) // 200 * 380
    for a in range(amount // 200 + 1):
        for b in range(amount // 300 + 1):
            for c in range(amount // 500 + 1):
                for a1 in range(amount // 1000 + 1):
                    for b1 in range(amount // 1200 + 1):
                        for c1 in range(amount // 1500 + 1):
                            if a*200 + b*300 + c*500 + a1*1000 + b1*1200 + c1*1500 == amount:
                                price = a*380 + b*550 + c*850 + a1*1520 + b1*1870 + c1*2244
                                if price < best_price:
                                    best_price = price
    return best_price


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]  #  ??????
            if j < w:
                cart[i][j] = cart[i-1][j]
            else:
                # ???????????????????????????????????????????????????????????????????????????????¨????
                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 = solve(amount)
        #print(result)
        result = solve2(amount)
        print(result)


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

Submission status: Accepted

Solution code:
h={15:2244,12:1870,10:1520,5:850,3:550,2:380}
m={0:0}

for i in range(50):
  if i in m:
    for k,v in h.items():
      m[i+k] = min(m.get(i+k,1e9),m[i]+v)

while True:
  n = input()
  if n == 0 : break
  print(m[n/100])

Submission status: Accepted

Solution code:
import sys
#from me.io import dup_file_stdin

def price(pack,unit_price,units,off):
    return pack//units*units*unit_price*(1.-off) + pack%units*unit_price

#@dup_file_stdin
def solve():
    while True:
        w = int(sys.stdin.readline())
        if w == 0 :return
        min = max([380*25,550*17,850*10])
        for a in range(0,w//200+1):
            need = w - a*200 
            for b in range(0,need//300+1):
                if((need-b*300)%500!=0):continue
                c = (need-b*300)//500
                p = price(a,380,5,0.2)+price(b,550,4,0.15)+price(c,850,3,0.12)
                if p < min:
                    min = p
        print("{:.0f}".format(min))
solve()

Submission status: Accepted

Solution code:
while True:
 N = int(input())
 if N==0: break
 ans = float('inf')
 for c200 in range(N//200+1):
  for c300 in range(N//300+1):
   for c500 in range(N//500+1):
    if 200 * c200 + c300 * 300 + c500 * 500 == N:
     ans = min(ans, 1520*(c200//5)+380*(c200%5)+1870*(c300//4)+550*(c300%4)+2244*(c500//3)+850*(c500%3))
 print(ans)

Submission status: Accepted

Solution code:
a=[1e4]*51
for i,j in[(2,380),(3,550),(5,850),(10,1520),(12,1870),(15,2244)]:
 a[i]=j
 for k in range(51-i):
  if a[k+i]>a[k]+j:a[k+i]=a[k]+j
for n in iter(input,'0'):print(a[int(n)//100])

Submission status: Accepted

Solution code:
a=[1e4]*51
for i,j in[(2,380),(3,550),(5,850),(10,1520),(12,1870),(15,2244)]:
 a[i]=j
 for k in range(51-i):a[k+i]=min(a[k]+j,a[k+i])
for n in iter(input,'0'):print(a[int(n)//100])

Submission status: Accepted

Solution code:
a=[1e4]*51
for i,j in[(2,380),(3,550),(5,850),(10,1520),(12,1870),(15,2244)]:
 a[i]=j
 for k in range(51-i):a[k+i]=min(a[k+i],a[k]+j)
for n in iter(input,'0'):print(a[int(n)//100])

Submission status: Accepted

Solution code:
def calc(A, B, C):
    da = A // 5
    na = A % 5
    db = B // 4
    nb = B % 4
    dc = C // 3
    nc = C % 3
    return da*1520 + na*380 + db*1870 + nb*550 + dc*2244 + nc*850

def f(a, b, c, g):
    if g == 0:
        return calc(a, b, c)
    if g < 0:
        return 10000000

    return min(f(a+1, b, c, g-2), f(a, b+1, c, g-3), f(a, b, c+1, g-5))

ans = [0,0,0,0,0,850,1100,1230,1400,1610,1520,\
       1950,1870,2070,2250,2244,2620,2624,2794,3004,3040,\
       3344,3390,3590,3740,3764,4120,4114,4314,4494,4488,\
       4864,4868,5038,5248,5284,5588,5634,5834,5984,6008,\
       6364,6358,6558,6738,6732,7108,7112,7282,7492,7528]

while True:
    N = int(input())
    if N == 0:
        break
    print(ans[N//100])

Submission status: Accepted

Solution code:
INF = 10 ** 20

def solve(n):
  ans = INF
  for i in range(n // 500 + 1):
    for j in range((n - 500 * i) // 300 + 1):
      if not (n - 500 * i - 300 * j) % 200:
        a = (n - 500 * i - 300 * j) // 200
        va = a // 5 * 1900 * 0.8  + a % 5 * 380
        vb = j // 4 * 2200 * 0.85 + j % 4 * 550
        vc = i // 3 * 2550 * 0.88 + i % 3 * 850
        ans = min(ans, va + vb + vc)
  print(int(ans))

while True:
  n = int(input())
  if not n:
    break
  solve(n)

Submission status: Accepted

Solution code:
# AOJ 0106 Discounts of Buckwheat 
# Python3 2018.6.18 bal4u

a = [ 2, 3, 5 ]
s = [ 380, 550, 850 ]
c = [ 10, 12, 15 ]
f = [ 1520, 1870, 2244 ]
tbl = [0]*60

def rec(i, v, cost):
	if i == 3:
		if (v <= 50 and tbl[v] == 0) or tbl[v] > cost: tbl[v] = cost
		return
	for j in range(0, 51-v, a[i]):
		cc = j // c[i] * f[i] + (j % c[i]) // a[i] * s[i]
		rec(i+1, v+j, cost+cc)

rec(0, 0, 0)
while True:
	n = int(input())
	if n == 0: break
	print(tbl[n//100])

Submission status: Accepted

Solution code:
def ceil(n, m):
  return n / m + 2 if n % m != 0 else n / m + 1

def gram(l):
  return 200 * l[0] + 300 * l[1] + 500 * l[2]

def price(l):
  def c(n, m, p, r):
    d = (n / m) * m
    return ((n - d) + d * r) * p

  return int(c(l[0], 5, 380, 0.80) + c(l[1], 4, 550, 0.85) + c(l[2], 3, 850, 0.88))

t = []
for amount in range(500, 5500, 100):
  for a in range(ceil(amount, 200)):
    for b in range(ceil(amount, 300)):
      for c in range(ceil(amount, 500)):
        if gram([a, b, c]) == amount:
          t.append([gram([a, b, c]), [a, b, c]])

while True:
  data = input()
  if data == 0:
    break
  s = []
  for x in t:
    if x[0] == data:
      s.append(price(x[1]))
  print sorted(s)[0]

Submission status: Accepted

Solution code:
def price(num_unit, shop):
    A, B, C = 0, 1, 2
    
    if shop == A:
        num_discount = (num_unit / 5) * 5
        return 380 * num_discount * 0.8 + 380 * (num_unit % 5)
    elif shop == B:
        num_discount = (num_unit / 4) * 4
        return 550 * num_discount * 0.85 + 550 * (num_unit % 4)
    else:
        num_discount = (num_unit / 3) * 3
        return 850 * num_discount * 0.88 + 850 * (num_unit % 3)

while True:
    quantity = int(raw_input())
    if quantity == 0: break

    comb = []
    for a in range(quantity / 200 + 1):
        for b in range(quantity / 200 + 1):
            for c in range(quantity / 200 + 1):
                if a * 200 + b * 300 + c * 500 == quantity:
                    comb.append([a, b, c])

    prices = []
    for c in comb:
        prices.append(price(c[0], 0) + price(c[1], 1) + price(c[2], 2))

    print int(min(prices))

Submission status: Accepted

Solution code:
w=[200,300,500,1000,1200,1500]
p=[380,550,850,1520,1870,2244]
dp=[2<<20]*5001
dp[0]=0
for i in xrange(6):
    for j in xrange(0,5000-w[i]+1,100):
        dp[j+w[i]] = min(dp[j+w[i]] , dp[j]+p[i])
while True:
    n=input()
    if n==0:
        break
    print dp[n]

Submission status: Accepted

Solution code:
while 1:
    w = int(raw_input())
    if w == 0: break
    minp = 9500
    for c in range(11):
        for b in range(17):
            for a in range(26):
                t = 200 * a + 300 * b + 500 * c
                if t > w: break
                if t == w:
                    p = int(380 * (a - a % 5) * 0.8 + 380 * (a % 5)
                            + 550 * (b - b % 4) * 0.85 + 550 * (b % 4)
                            + 850 * (c - c % 3) * 0.88 + 850 * (c % 3))
                    minp = min(minp, p)
    print minp

Submission status: Accepted

Solution code:

import sys


class Item:
    def __init__(self, amount, price):
        self.amount = amount
        self.price = price


items = [ Item(200, 380),                   #  380
          Item(300, 550),                   #  550
          Item(500, 850),                   #  850
          Item(200 * 5, 380 * 5 * 0.8),     # 1520
          Item(300 * 4, 550 * 4 * 0.85),    # 1870
          Item(500 * 3, 850 * 3 * 0.88) ]   # 2244


dp = [sys.maxint] * 5001
dp[0] = 0
for item in items:
    for i in xrange(0, 5001):
        if i + item.amount <= 5000:
            dp[i + item.amount] = min(dp[i + item.amount], dp[i] + item.price)

while True:
    amount = int(sys.stdin.readline())
    if amount == 0:
        exit()
    print int(dp[amount])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    price_table = (
        0, 0, 380, 550, 760, 850, 1100, 1230, 1400, 1610, 1520, 1950,
        1870, 2070, 2250, 2244, 2620, 2624, 2794, 3004, 3040, 3344,
        3390, 3590, 3740, 3764, 4120, 4114, 4314, 4494, 4488, 4864,
        4868, 5038, 5248, 5284, 5588, 5634, 5834, 5984, 6008, 6364,
        6358, 6558, 6738, 6732, 7108, 7112, 7282, 7492, 7528
        )
    while 1:
        weight = int(readline())
        if not weight:
            exit()
        print(price_table[weight//100])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
r = 51
wc = [[15,2244],[10,1520],[12,1870],[5,850],[3,550],[2,380]]
dp = [0]*r
for w,c in wc:
	dp[w] = c
	for i in range(r - w):
		if dp[i] > 0 and (dp[i + w] == 0 or dp[i + w] > dp[i] + c):
			dp[i + w] = dp[i] + c

while 1:
	n = input()
	if n == 0: break
	print dp[n/100]

Submission status: Accepted

Solution code:
r,x = 51,2**31
wc = [[15,2244],[10,1520],[12,1870],[5,850],[3,550],[2,380]]
dp = [x]*r
for w,c in wc:
	dp[w] = c
	for i in range(r - w):
		if dp[i] < x and dp[i + w] > dp[i] + c:
			dp[i + w] = dp[i] + c

while 1:
	n = input()
	if n == 0: break
	print dp[n/100]

Submission status: Accepted

Solution code:
""" 
A店：200g,380y,20%/5 → 1.9y/g
B店：300g,550y,15%/4 → 1.83y/g
C店：500g,850y,12%/3 → 1.7y/g
380*5 *0.8 = 1520   304/1つ
550*4 *0.85 = 1870  467.5/1つ
850*3 *0.88 = 2244  748/1つ
"""
# 購入数は50g刻みと明言されているので

P = [2,10, 3,12, 5,15]
Q = [380,1520, 550,1870, 850,2244]
MAX = 50
Range = [0] + [1000000]*MAX

for p,q in zip(P,Q):
    for i in range(MAX - p+1):
        Range[i+p] = min(Range[i+p],Range[i]+q)

while True:
    v = int(input())
    if v==0:
        break
    print(Range[v//100])

Submission status: Accepted

Solution code:
P = [2, 10, 3, 12, 5, 15]
Q = [380, 1520, 550, 1870, 850, 2244]
MAX = 50
Range = [0] + [1000000] * MAX

for p, q in zip(P, Q):
    for i in range(MAX - p + 1):
        Range[i + p] = min(Range[i + p],Range[i] + q)
while 1:
    v = int(input())
    if v == 0:
        break
    print(Range[v // 100])

Submission status: Accepted

Solution code:
P = [2, 10, 3, 12, 5, 15]
Q = [380, 1520, 550, 1870, 850, 2244]
L = 50
R = [0] + [1e9]*L
for p, q in zip(P, Q):
    for i in range(L-p+1):
        R[i+p] = min(R[i+p], R[i] + q)
while 1:
    v = int(input())
    if v == 0:
        break
    print(R[v//100])