Problem:


Score : 300 points

Problem Statement

Snuke is making sugar water in a beaker.
Initially, the beaker is empty. Snuke can perform the following four types of operations any number of times. He may choose not to perform some types of operations.

Operation 1: Pour 100A grams of water into the beaker.

Operation 2: Pour 100B grams of water into the beaker.

Operation 3: Put C grams of sugar into the beaker.

Operation 4: Put D grams of sugar into the beaker.

In our experimental environment, E grams of sugar can dissolve into 100 grams of water.

Snuke will make sugar water with the highest possible density.

The beaker can contain at most F grams of substances (water and sugar combined), and there must not be any undissolved sugar in the beaker.
Find the mass of the sugar water Snuke will make, and the mass of sugar dissolved in it.
If there is more than one candidate, any of them will be accepted.

We remind you that the sugar water that contains a grams of water and b grams of sugar is \frac{100b}{a + b} percent.
Also, in this problem, pure water that does not contain any sugar is regarded as 0 percent density sugar water.

Constraints

1 \leq A < B \leq 30

1 \leq C < D \leq 30

1 \leq E \leq 100

100A \leq F \leq 3 000

A, B, C, D, E and F are all integers.

Inputs

Input is given from Standard Input in the following format:

A B C D E F

Outputs

Print two integers separated by a space.
The first integer should be the mass of the desired sugar water, and the second should be the mass of the sugar dissolved in it.

Sample Input 1

1 2 10 20 15 200

Sample Output 1

110 10

In this environment, 15 grams of sugar can dissolve into 100 grams of water, and the beaker can contain at most 200 grams of substances.

We can make 110 grams of sugar water by performing Operation 1 once and Operation 3 once.
It is not possible to make sugar water with higher density.
For example, the following sequences of operations are infeasible:

If we perform Operation 1 once and Operation 4 once, there will be undissolved sugar in the beaker.

If we perform Operation 2 once and Operation 3 three times, the mass of substances in the beaker will exceed 200 grams.

Sample Input 2

1 2 1 2 100 1000

Sample Output 2

200 100

There are other acceptable outputs, such as:

400 200

However, the output below is not acceptable:

300 150

This is because, in order to make 300 grams of sugar water containing 150 grams of sugar, we need to pour exactly 150 grams of water into the beaker, which is impossible.

Sample Input 3

17 19 22 26 55 2802

Sample Output 3

2634 934



Sample input:
1 2 10 20 15 200


Sample output:
110 10

Submission status: Runtime Error

Solution code:
from itertools import product

a, b, c, d, e, f = map(int, input().split())

lima = [100 * a * i for i in range(f // (100 * a) + 1)]
limb = [100 * b * i for i in range(f // (100 * b) + 1)]
setw = set([i + j for i, j in product(lima, limb) if 0 < i + j <= f])
limc = [c * i for i in range(f // c + 1)]
limd = [d * i for i in range(f // d + 1)]
sets = set([i + j for i, j in product(limc, limd) if 0 < i + j <= f])

cnt = 0
for w in setw:
    for s in sets:
        if cnt <= 100 * s / w <= e and s + w <= f:
            cnt = 100 * s / w
            ans = s + w, s
            if s == e * w // 100:
                print(*ans)
                exit()
else:
    print(*ans)

Submission status: Runtime Error

Solution code:
A,B,C,D,E,F = map(int,input().split())

conc = 0
total = 0

for a in range(0,31):
  for b in range(0,31):
    water = (A * a + B * b) * 100
    if water > F:
      break
    else:
      for c in range(3001):
        water = (A * a + B * b) * 100
        
        if water == 0:
          break
        #探索中の水の量に溶かせられる砂糖の限界量
        sugar_limit = int(water * E / 100)
        #操作Cで投入された砂糖の量
        sugarC = c * C
        
        if sugarC > sugar_limit:
          break
        #ビーカーに溶かせる容量
        else:
          rest = F - water - sugarC
          #水に溶かせられる砂糖量
          sugar_rest = sugar_limit - sugarC
          
          if rest < 0:
            break
          
          else:
            #操作Dで溶かせられる砂糖の量
            sugarD = (min(rest,sugar_rest) // D) * D
            sugar = sugarC + sugarD
            temp = (sugar) / (water + sugar)
            if conc < temp and temp < E:
              conc = temp
              total = water + sugar
              ans = [total,sugar]
        
print(ans[0],ans[1])

Submission status: Runtime Error

Solution code:
a, b, c, d, e, f = map(int, input().split())
limit = 100 * e / (100 + e)
mx = -1

waters = set()
for i in range(0, f // a + 1, 100 * a):
    for j in range(0, (f - i * a) // b + 1, 100 * b):
        waters.add(i + j)

sugars = set()
for i in range(0, f // c + 1, c):
    for j in range(0, (f - c) // d + 1, d):
        sugars.add(i + j)

for i in waters:
    for j in sugars:
        if i + j > f or i + j == 0:
            break
        noudo = (100 * j / (i + j))
        if noudo <= limit:
            if noudo > mx:
                mx = noudo
                x, y = i + j, j
print(x, y)

Submission status: Runtime Error

Solution code:
A,B,C,D,E,F = list(map(int,input().split()))

tmp = 0
for i in range(30):
  a = A*i
  if a*100 >= F:
    break
  for j in range(30):
    b = B*j
    if a+b == 0:
      continue
    w = (a+b)*100
    if w >= F:
      break
    for k in range(3000):
      c = C*k
      for l in range(3000):
        d = D*l
        s = c+d
        if w + s >= F:
          break
        if (c+d) <= (a+b)*E:
          if (s*100)/w > tmp:
            tmp = (s*100)/w
            ans = [s+w,s]
        else:
          break

print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
a,b,c,d,e,f=map(int,input().split())
maxsugar=f*e/(100+e)
maxwater=f*100/(100+e)
#print(maxsugar,maxwater)
sugar=[]
for i in range(int(maxsugar)//min(c,d)+2):
    for j in range(int(maxsugar)//min(c,d)+2):
        x=i*c+j*d
        if x<=maxsugar:
            sugar.append(x)
#print(sugar)
water=[]
for i in range(int(maxwater//100+2)//min(a,b)+1):
    for j in range(int(maxwater//100+2)//min(a,b)+1):
        y=i*a+j*b
        water.append(y)
#print(water)
water.remove(0)
ansl=[]
for i in sugar:
    for j in water:
        z=i/(j*100+i)
        xyz=i+j*100
        if xyz<=f and z<=e/(100+e):
            ansl.append((i,j,z))
s,t,r=sorted(ansl,key=lambda x:x[-1])[-1]
print(s+t*100,s)

Submission status: Runtime Error

Solution code:
import fractions as frac
a, b, c, d, e, f = map(int, input().split())
memo=[[(-1, -1)]*10000 for i in range(1000)]
func = lambda t: frac.Fraction(t[0], t[1]) if t[1]>0 else -10
def dp(s, w):
    if w*e<s or w*100+s>f:
        return (-1, -1)
    m=memo[s][w]
    if m[0]>0:
        return memo[s][w]
    p0=(s,w) 
    p1=dp(s, w+a)
    p2=dp(s, w+b)
    p3=dp(s+c, w)
    p4=dp(s+d, w)
    memo[s][w]=max(p0, p1, p2, p3, p4, key = func) if w>0 else max(p1, p2, key = func)
    return memo[s][w]
    
ans=dp(0,0)
print(ans[0]+ans[1]*100, ans[0])

Submission status: Runtime Error

Solution code:
import fractions as frac
a, b, c, d, e, f = map(int, input().split())
memo=[[(-1, -1)]*10000 for i in range(1000)]
func = lambda t: frac.Fraction(t[0], t[1]  ) 
def dp(s, w):
    if w*e<s or w*100+s>f:
        return (-1, -1)
    m=memo[s][w]
    if m[0]>0:
        return memo[s][w]
    p0=(s,w) 
    p1=dp(s, w+a)
    p2=dp(s, w+b)
    p3=dp(s+c, w)
    p4=dp(s+d, w)
    memo[s][w]=max(p0, p1, p2, p3, p4, key = func) if w>0 else max(p1, p2, key = func)
    return memo[s][w]
    
ans=dp(0,0)
print(ans[0]+ans[1]*100, ans[0])

Submission status: Runtime Error

Solution code:
# C sugar water
from collections import deque
def noudo(water, sugar):
    if water+sugar==0: return 0
    return 100*sugar/(water+sugar)

A,B,C,D,E,F = map(int, input().split())
q = deque([(0,0)]) # water, sugar
max_noudo = 0
ans = None
while q:
    water,sugar = q.popleft()
    cur = noudo(water, sugar)
    if cur>max_noudo:
        ans = (water, sugar)
        max_noudo = cur
    for dw,ds in [(100*A, 0), (100*B, 0), (0,C), (0,D)]:
        if noudo(water+dw, sugar+ds)>noudo(100, E) or water+dw+sugar+ds>F: continue
        q.append((water+dw, sugar+ds))
        
water, sugar = ans
print(water+sugar, sugar)

Submission status: Runtime Error

Solution code:
a, b, c, d, e, f = map(int, input().split())

dp_w = [[0 for j in range(31)] for i in range(3)]

for j in range(31):
    if j<a:
        dp_w[1][j] = dp_w[0][j]
    elif j==a:
        dp_w[1][j] = 1
    else:
        if dp_w[0][j]==1 or dp_w[1][j-a]==1:
            dp_w[1][j] = 1
 
for j in range(31):
    if j<b:
        dp_w[2][j] = dp_w[1][j]
    elif j==b:
        dp_w[2][j] = 1
    else:
        if dp_w[1][j]==1 or dp_w[2][j-b]==1:
            dp_w[2][j] = 1           

dp_s = [[0 for j in range(3001)] for i in range(3)]

for j in range(3001):
    if j<c:
        dp_s[1][j] = dp_s[0][j]
    elif j==c:
        dp_s[1][j] = 1
    else:
        if dp_s[0][j]==1 or dp_s[1][j-c]==1:
            dp_s[1][j] = 1
 
for j in range(3001):
    if j<d:
        dp_s[2][j] = dp_s[1][j]
    elif j==d:
        dp_s[2][j] = 1
    else:
        if dp_s[1][j]==1 or dp_s[2][j-d]==1:
            dp_s[2][j] = 1  

nodo = 0
ans_s = 0
ans_all = 0

for i in range(31):
    if dp_w[2][i]==1:
        Max_s = e*i
        now_ans = 0
        now_all = 0
        for j in range(3001):
            if dp_s[2][j]==1 and j+100*i<=f and j<=Max_s:
                now_ans = j
                now_all = j+100*i
        if nodo<now_ans/now_all:
            nodo = now_ans/now_all
            ans_s = now_ans
            ans_all = now_all
      
ans = [str(ans_all), str(ans_s)]
        
print(' '.join(ans))

Submission status: Runtime Error

Solution code:
A, B, C, D, E, F=map(int, input().split())
for i in range(31):
    w=100*A*i
    s=0
    if s+w>F:
        break
    for j in range(31):
        w=100*A*i+100*B*j
        s=0
        if s+w>F:
            break
        for k in range(3001):
            w=100*A*i+100*B*j
            s=C*k
            if s+w>F:
                break
            for l in range(3001):
                w=100*A*i+100*B*j
                s=C*k+D*l
                if s+w>F:
                    break
                if w!=0 and s*(100+E)<=(s+w)*E and sans*(s+w)<=s*(sans+wans) and w+s<=F:
                    sans=s
                    wans=w
                #print(sans,sans+wans)
print(sans+wans,sans)

Submission status: Runtime Error

Solution code:
a, b, c, d, e, f = map(int, input().split())
x = set()
y = set()
for A in range(0, f + 1, 100 * a):
    for B in range(0, f + 1, 100 * b):
        if A + B > f:
            break
        if A + B:
            x.add(A + B)
for C in range(0, f + 1, c):
    for D in range(0, f + 1, d):
        if C + D > f:
            break
        y.add(C + D)
ans = 0
for X in x:
    for Y in y:
        if X + Y <= f and 100 * Y / X <= e:
                if ans < Y / (X + Y):
                    ans = Y / (X + Y)
                    w = X
                    s = Y
print(w + s, s)

Submission status: Runtime Error

Solution code:
a, b, c, d, e, f = map(int, input().split())
x = set()
y = set()
for A in range(0, f + 1, 100 * a):
    for B in range(0, f + 1, 100 * b):
        if A + B:
            x.add(A + B)
for C in range(0, f + 1, c):
    for D in range(0, f + 1, d):
        y.add(C + D)
ans = 0
for X in x:
    for Y in y:
        if X + Y <= f and 100 * Y / X <= e:
                if ans < Y / (X + Y):
                    ans = Y / (X + Y)
                    w = X
                    s = Y
print(w + s, s)

Submission status: Runtime Error

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

maxd = -1
ans = None

A, B, C, D, E, F = reads()
for i, j, k in product(range(31), range(31), range(3001)):
  water100 = A * i + B * j
  if C * k > water100 * E or water100 == 0:
    continue
  l = (water100 * E - C * k) // D
  sugar = C * k + D * l
  mass = water100 * 100 + sugar
  density = sugar / mass
  if mass <= F and maxd < density:
    maxd = density
    ans = (mass, sugar)

print(ans[0], ans[1])

Submission status: Runtime Error

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

maxd = 0
ans = None

A, B, C, D, E, F = reads()
for i, j, k in product(range(31), range(31), range(3001)):
  water100 = A * i + B * j
  if C * k > water100 * E or water100 == 0:
    continue
  l = (water100 * E - C * k) // D
  sugar = C * k + D * l
  mass = water100 * 100 + sugar
  density = sugar / mass
  if mass <= F and maxd < density:
    maxd = density
    ans = (mass, sugar)

print(ans[0], ans[1])

Submission status: Runtime Error

Solution code:
import sys
a,b,c,d,e,f=map(int,input().split())
ans=0
s=0
t=0
for i in range(f//100+1):
    if i==0 and j==0:
        continue
    w=(f-100*a*i)//100
    for j in range(w+1):
        x=a*i+b*j
        for k in range(x*e//c+1):
            if k==0 and l==0:
                continue
            v=(x*e-c*k)//d
            for l in range(v+1):
                y=c*k+d*l
                if 100*x+y <=f:
                    p=100*y/(100*x+y)
                    if ans<p:
                        s=100*x+y
                        t=y
print(s,t)

Submission status: Runtime Error

Solution code:
import sys
a,b,c,d,e,f=map(int,input().split())
ans=0
s=0
t=0
for i in range(f//100+1):
    if i==0 and j==0:
        continue
    w=(f-100*a*i)//100
    for j in range(w+1):
        x=a*i+b*j
        for k in range(x*e//c+1):
            v=(x*e-c*k)//d
            for l in range(v+1):
                y=c*k+d*l
                if 100*x+y <=f:
                    p=100*y/(100*x+y)
                    if ans<p:
                        s=100*x+y
                        t=y
print(s,t)

Submission status: Runtime Error

Solution code:
A,B,C,D,E,F=map(int,input().split())
conc = 0.0
liq,sug=0,0
for a in range(31):
  for b in range(16):
    for c in range(31):
      for d in range(16):
        if 100*a+100*b+c+d <= F and  c+d <= (a+b)*E:
          if conc < 100*(c+d)/(100*(a+b)+c+d):
            conc = 100*(c+d)/(100*(a+b)+c+d)
            liq = 100*(a+b)
            sug = c+d
print(liq,sug)

Submission status: Runtime Error

Solution code:
A,B,C,D,E,F = map(int,input().split())

water_sugar = []
sugar_best = []
max_sugar = 0

for a in range(0,31):
    water = A*a
    sugar = E*water
    if water==0:
        pass
    elif (water*100)>F:
        break
    elif (water*100)+sugar>F:
        s = F-(water*100)
        water_sugar.append([water*100,s])
    elif (water*100)+sugar<=F:
        s = sugar
        water_sugar.append([water*100,s])
    if s>max_sugar: max_sugar=s
    for b in range(1,31):
        water += B
        sugar = E*water
        if (water*100)>F:
            break
        elif (water*100)+sugar>F:
            s = F-(water*100)
            water_sugar.append([water*100,s])
        elif (water*100)+sugar<=F:
            s = sugar
            water_sugar.append([water*100,s])
        if s>max_sugar: max_sugar=s
        

#print(water_sugar)
#print(max_sugar)

sugar = []
c=0
while(True):
    s = c*C
    if s<=max_sugar:
        sugar.append(s)
    else:
        break
    while(True):
        s += D
        if s<=max_sugar:
            sugar.append(s)
        else:
            break
    c+=1
sugar = sorted(sugar,reverse=True)

#print(sugar)

for ws in water_sugar:
    for s in sugar:
        if s<=ws[1]: break
    ws[1] = s
    sugar_best.append((100*ws[1])/(ws[0]+ws[1]))
    
best = water_sugar[sugar_best.index(max(sugar_best))]

print(best[0]+best[1],best[1])

Submission status: Runtime Error

Solution code:
A, B, C, D, E, F = map(int, input().split())
A, B = 100 * A, 100 * B
W = set()
S = set()

for i in range(F // A+1):
    for j in range(F // B+1):
        w = A * i + B * j
        if w <= F:
            W.add(w)

for i in range(F // C+1):
    for j in range(F // D+1):
        s = C * i + D * j
        if s <= F:
            S.add(s)

S.remove(0)
W.remove(0)
max_rat = -24
for w in W:
    for s in S:
        if w + s <= F and s <= w / 100 * E:
            rat = s / (s + w)
            if rat > max_rat:
                x, y, max_rat = w, s, rat

print(x + y, y)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations

def inpl(): return tuple(map(int, input().split()))

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    for k in range(N):
        if A[i][j] > A[i][k] + A[k][j]:
            exist = False
            break
    
    if not exist:
        break
    
    for k in range(N):
        if i == k or j == k:
            pass
        elif A[i][j] == A[i][k] + A[k][j]:
            vervose = True
            break
        
    if not vervose:
        res += A[i][j]
if exist:
    print(res)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
# coding:utf-8

input=raw_input()
list=input.split(" ")
for i in range(len(list)):
    list[i]=int(list[i])

f=list[5]

# xが取り得る値
listx=[]
a=list[0]
b=list[1]

i=0
while True:
   if i*a*100>f:
       break
   j=0
   while True:
      x=i*a*100+j*b*100
      if x > f:
          break;
      if x not in listx:
          listx.append(int(x))
      j+=1 
   i+=1 

# yが取り得る値
listy=[]
c=list[2]
d=list[3]

# yが水に溶け切れる最大値
f2=f*e/(100.0+e)

i=0
while True:
   if i*c>f2:
       break
   j=0
   while True:
      y=i*c+j*d
      if y > f:
          break;
      if y not in listy:
          listy.append(int(y))
      j+=1 
   i+=1 

# 全てのxとyの組み合わせについてfを超えないか、および溶け切れるかを調べる
lengthx=len(listx)
lengthy=len(listy)

xy_max=0
y_max=0
noudo_max=0
for i in range(lengthx):
    for j in range(lengthy):
        x=listx[i]
        y=listy[j]
        if x+y>f:
            continue
        noudo=float(y)/(x+y)
        if noudo>noudo_max:
            xy_max=x+y
            y_max=y
            noudo_max=noudo

print xy_max
print " "
print y_max

Submission status: Runtime Error

Solution code:
import numpy as np

def ceil(a):
    return int(np.ceil(a))

def sol2():
    A,B,C,D,E,F = map(int, input().split(' '))
    na, nb, nc, nd = ceil(F/A/100),ceil(F/B/100),ceil(E*F/C/100),ceil(E*F/D/100) 
    sug = np.arange(0,nc).reshape(1,1,nc,1)*C+np.arange(0,nd).reshape(1,1,1,nd)*D
    wat = np.arange(0,na).reshape(na,1,1,1)*A*100+np.arange(0,nb).reshape(1,nb,1,1)*B*100
    sug2=np.unique(sug[sug<=F*F/100])
    wat2=np.unique(wat[wat<=F])[1:]
    tot =  wat2.reshape(len(wat2),1) + sug2
    e2 = E/(100+E)
    dense = (sug2/tot)[tot<=F]
    
    if E==0:
        print(wat2[1],0)
        return
    
    maxi = np.argmax(dense[dense<=e2])
    stot = tot[tot<=F][dense<=e2]
    ssug = (sug2 + tot*0)[tot<=F][dense<=e2]
    
    if dense[maxi] ==0:
        print(wat2[1],0)
    else:
        print(int(stot[maxi]),int(ssug[maxi]))
sol2()

Submission status: Runtime Error

Solution code:
import numpy as np

def sol():
    A,B,C,D,E,F = map(int, input().split(' '))
    na, nb, nc, nd = int(F/A/100),int(F/A/100),int(E*F/E/100),int(E*F/D/100) 
    sug = np.arange(0,nc).reshape(1,1,nc,1)*C+np.arange(0,nd).reshape(1,1,1,nd)*D
    wat = np.arange(0,na).reshape(na,1,1,1)*A*100+np.arange(0,nb).reshape(1,nb,1,1)*B*100
    tot =  wat + sug
    tot[0,0,0,0]=1
    dense = sug/tot*100
    maxi = np.argmax(dense[tot<F][dense[tot<F]<E])
    swat = (wat + np.ndarray((na,nb,nc,nd))*0)[tot<F][dense[tot<F]<E]
    ssug = (sug + np.ndarray((na,nb,nc,nd))*0)[tot<F][dense[tot<F]<E]
    print(swat[maxi],ssug[maxi])
    
sol()

Submission status: Runtime Error

Solution code:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

ans = 0
for i in range(n) :
    for j in range(i+1, n) :
        for k in range(n) :
            if i == k or j == k:
                continue
            
            d = A[i][k] + A[k][j]
            if d == A[i][j] :
                ans += d
            elif d < A[i][j] :
                print(-1)
                exit()

print(ans)

Submission status: Runtime Error

Solution code:
def main() :
    n = int(input())
    A = []
    for _ in range(n) :
        A.append(list(map(int, input().split())))

    ans = sum([sum(_A) for _A in A])
    for k in range(n) :
        for i in range(n) :
            for j in range(n) :
                if i == k :
                    break
                elif j == k :
                    continue
                
                d = A[i][k] + A[k][j]
                if d == A[i][j] :
                    ans -= d
                elif d < A[i][j] :
                    print(-1)
                    exit()

    print(ans//2)

main()

Submission status: Runtime Error

Solution code:
a,b,c,d,e,f = map(int, input().split())

w = [i+j for i in range(0,f+1,100*a) for j in range(0,f+1,100*b) if i+j <= f]
s = [i+j for i in range(0,f+1,c) for j in range(0,f+1,d) if i+j <= f]

W = w[0]
S = 0
for ww in w :
    for ss in s :
        if ww+ss > f or ww == 0:
            continue
        elif ss/(ss+ww) > S/(W+S) and e >= 100*ss/ww:
            W = ww
            S = ss

print(W+S, S)

Submission status: Runtime Error

Solution code:
a,b,c,d,e,f = map(int, input().split())

w = [i+j for i in range(0,f+1,100*a) for j in range(0,f+1,100*b) if i+j <= f]
s = [i+j for i in range(0,f+1,c) for j in range(0,f+1,d) if i+j <= f]

W = f//(100*b)
S = 0
for ww in w :
    for ss in s :
        if ww+ss > f or ww == 0:
            continue
        elif ss/(ss+ww) > S/(W+S) and e >= 100*ss/ww:
            W = ww
            S = ss

print(W+S, S)

Submission status: Runtime Error

Solution code:
test:
aaa

Submission status: Runtime Error

Solution code:
A,B,C,D,E,F = list(map(int,input().split()))
A = 100*A
B = 100*B

a = int(F/A)
b = int(F/B)


hoge = 0

dp = [[0 for i in range(a+1)]for i in range(b+1)]
Na = [[0 for i in range(a+1)]for i in range(b+1)]
noudo = [[0 for i in range(a+1)]for i in range(b+1)]

for i in range(a+1):
    for j in range(b+1):
        if A*i+B*j < F:
            dp[i][j] = A*i+B*j
        c = int(E*dp[i][j]/(100*C))
        d = int(E*dp[i][j]/(100*D))
        for k in range(c+1):
            for m in range(d+1):
                if C*k+D*m <= F-dp[i][j]  and C*k+D*m < E*dp[i][j]/100:
                    Na[i][j] = max(Na[i][j],C*k+D*m)

for i in range(a+1):
    for j in range(b+1):
        if dp[i][j] != 0 and Na[i][j] != 0:
            noudo[i][j] = Na[i][j]/(dp[i][j]+Na[i][j])
        if hoge <= noudo[i][j]:
            res_i = i
            res_j = j
            hoge = noudo[i][j]

print(dp[res_i][res_j]+Na[res_i][res_j],Na[res_i][res_j])

Submission status: Runtime Error

Solution code:
import sys
import socket

if socket.gethostname() == 'N551J':
    sys.stdin = open('a1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    a, b, c, d, e, f = read_int_list()
    best_sugar = 0
    best_total = a
    for i in range(31):
        for j in range(31):
                for k in range(3001):
                    water = i * 100 * a + j * 100 * b
                    if water + k * c <= f and k * c * 100 <= water * e:
                        l1 = int((f - water - k * c) / d)
                        l2 = int((water * e // 100 - k * c) / d)
                        l = min(l1, l2)
                        if (i, j, k, l) != (0, 0):
                            sugar = k * c + l * d
                            total = water + sugar
                            density = sugar / total
                            best_density = best_sugar / best_total
                            if density > best_density:
                                best_sugar = sugar
                                best_total = total
    return best_total, best_sugar


def main():
    res = solve()
    print(*res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
A, B, C, D, E, F = map(int, raw_input().split())
def weight(suger, water):
    return suger + water*100

max_c = F/(100+E)*E / C
max_d = F/(100+E)*E / D
max_a = F/100 / A
max_b = F/100 / B
suger_list = []
for i in range(max_c+1):
    for j in range(max_d+1):
        if i*C+j*D not in suger_list:
            suger_list.append(i*C+j*D)
suger_list = sorted(suger_list)
water_list = []
for i in range(max_a+1):
    for j in range(max_b+1):
        if i*A+j*B not in water_list:
            water_list.append(i*A+j*B)
water_list = sorted(water_list)[1:]
i = 0
j = 0
water = water_list[j]
while True:
    if (suger_list[i])*1. / water <= E and weight(suger_list[i], water) <= F:
        suger = suger_list[i]
        if i >= len(suger_list)-1:
            break
        i += 1
    elif j+1 <= len(water_list) and weight(suger, water_list[j+1]) <= F:
            water = water_list[j+1]
            j += 1
    else:
        break
print weight(suger, water), suger

Submission status: Runtime Error

Solution code:
waters = set([a+b for b in range(0, F+1, B) for a in range(0, F+1, A) if a+b <= F])

res_water = 0
res_sugar = 0
max_ratio = 0

for w in sorted(waters):
    sugars = [c+d for c in range(0, int(w/100)*E+1, C)
                         for d in range(0, int(w/100)*E+1, D) 
                             if (c+d+w <= F) and (c+d <=int(w/100)*E)]
    sugar = max(sugars)
    #print(sugars)
    if w+sugar==0:
        continue
    if 100*sugar / (w+sugar) > max_ratio:
        max_ratio = 100*sugar / (w+sugar)
        res_water = w
        res_sugar = sugar
print("{} {}".format(res_water+res_sugar, res_sugar))

Submission status: Runtime Error

Solution code:
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
B = [e[:] for e in A]

for k in range(n):
    for i in range(n):
        for j in range(n):
            B[i][j] = min(B[i][k] + B[k][j], B[i][j])
ok = 1
for i in range(n):
    for j in range(n):
        if A[i][j] != B[i][j]:
            ok = 0
if not ok:
    print(-1)
    exit(0)

ans = 0
for i in range(n):
    for j in range(i+1, n):
        need = 1
        for k in range(n):
            if i == k or j == k:
                continue
            if A[i][k] + A[k][j] == A[i][j]:
                need = 0
        if need:
            ans += A[i][j]
print(ans)

Submission status: Runtime Error

Solution code:
a,b,c,d,e,f = map(int,input().split())


from itertools import product
water = set()

for i,j in product(range(f//(a*100)+2),range(f//(100*b)+2)):
  n = a*i+b*j
  if n <= f:
    water.add(n)

water = sorted(water)

salt = set()

for i,j in product(range(f//c+2),range(f//d+2)):
  n = c*i+d*j
  if n <= f:
    salt.add(n)

from bisect import bisect_left

bs,bw = 0,1
salt = sorted(salt)
for s in salt:
  w = s/e
  i = bisect_left(water,w)
  w = water[i]
  if 100*w + s > f:
    break
  if bs*w < bw*s:
    bs,bw = s,w

print(bs+100*bw,bs)

Submission status: Runtime Error

Solution code:
a,b,c,d,e,f = map(int,input().split())


from itertools import product
water = set()

for i,j in product(range(f//(a*100)+1),range(f//(100*b)+1)):
  n = a*i+b*j
  if n <= f:
    water.add(n)

water = sorted(water)

salt = set()

for i,j in product(range(f//c+1),range(f//d+1)):
  n = c*i+d*j
  if n <= f:
    salt.add(n)

from bisect import bisect_left

bs,bw = 0,1
salt = sorted(salt)
for s in salt:
  w = s/e
  i = bisect_left(water,w)
  w = water[i]
  if 100*w + s > f:
    break
  if bs*w < bw*s:
    bs,bw = s,w

print(bs+100*bw,bs)