Problem:


　最高のピザ (Best Pizza)  

  問題

 K 理事長は，JOI 市の中心部にある JOI ピザ店の常連客である．彼はある事情により，今月から節約生活を始めることにした．そこで彼は，JOI ピザ店で注文できるピザのうち，1 ドルあたりのカロリーが最大となるようなピザを注文したいと思った．このようなピザを「最高のピザ」と呼ぶことにしよう．「最高のピザ」は 1 種類とは限らない．

JOI ピザでは N 種類のトッピングから何種類かを自由に選び，基本の生地の上に載せたものを注文することができる．同種のトッピングを 2 つ以上載せることはできない．生地にトッピングを 1 種類も載せないピザも注文できる．生地の値段は A ドルであり，トッピングの値段はいずれも B ドルである．ピザの値段は，生地の値段と載せたトッピングの値段の合計である．すなわち，トッピングを k 種類 (0 ≦ k ≦ N) 載せたピザの値段は A + k × B ドルである．ピザ全体のカロリーは，生地のカロリーと載せたトッピングのカロリーの合計である．

生地の値段とトッピングの値段，および，生地と各トッピングのカロリーの値が与えられたとき，「最高のピザ」の 1 ドルあたりのカロリー数を求めるプログラムを作成せよ．

  入力

入力は N + 3 行からなる．

1 行目にはトッピングの種類数を表す 1 つの整数 N (1 ≦ N ≦ 100) が書かれている．2 行目には 2 つの整数 A, B  (1 ≦ A ≦ 1000，1 ≦ B ≦ 1000) が空白を区切りとして書かれている．A は生地の値段，B はトッピングの値段を表す．3 行目には，生地のカロリー数を表す 1 つの整数 C (1 ≦ C ≦ 10000) が書かれている．

3 + i 行目 (1 ≦ i ≦ N) には，i 番目のトッピングのカロリー数を表す 1 つの整数 Di (1 ≦ Di ≦ 10000) が書かれている．

  出力

「最高のピザ」の 1 ドルあたりのカロリー数を 1 行で出力せよ．ただし，小数点以下は切り捨てて整数値で出力せよ．

  入出力例

入力例 1

3
12 2
200
50
300
100

出力例 1

   

37

入出力例 1 では，2 番目と 3 番目のトッピングを載せると，200 + 300 + 100 = 600 カロリーで 12 + 2 × 2 = 16 ドルのピザになる．

このピザは 1 ドルあたり 600 / 16 = 37.5 カロリーになる．これが「最高のピザ」となるので，37.5 の小数点以下を切り捨てた 37 を出力する．

入力例 2
  

  

4
20 3
900
300
100
400
1300

出力例 2

   

100

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3
12 2
200
50
300
100


Sample output:
37

Submission status: Wrong Answer

Solution code:
n = input()
a, b = map(int, raw_input().split())
ca = input()
max = ca / a
cb = [input() for i in range(n)]
sum_b = a
sum_cb = ca
for t in reversed(sorted(cb)):
    sum_b += b
    sum_cb += t
    print sum_b, sum_cb
    if max <= sum_cb / sum_b: max = sum_cb / sum_b
    else: break
print max

Submission status: Wrong Answer

Solution code:
num_choice = int(raw_input())
price=list(map(int,raw_input().split()))
base_cal = int(raw_input())
topping_cal = []
for i in range (num_choice):
	topping_cal.append(int(raw_input()))
topping_cal.sort()
topping_cal.reverse()
average_cal = int(base_cal / price[0])
for i in range (num_choice):
	new_average = int((sum(topping_cal[:i+1]) + base_cal) / (price[0] + price[1] * (i+1)) )
	if new_average > average_cal:
		average_cal = new_average
	else:
		break
print average_cal

Submission status: Wrong Answer

Solution code:
N = input()
A, B = map(int, raw_input().split())
C = input()
D = [input() for i in range(N)]
D.sort()
topping = D[-2:]
k = len(topping)
price = A + B * k
calory = C + sum(topping)
print calory/price

Submission status: Accepted

Solution code:
n = input()
a, b = map(int, raw_input().split())
ca = input()
max = ca / a
cb = [input() for i in range(n)]
sum_b = a
sum_cb = ca
for t in reversed(sorted(cb)):
    sum_b += b
    sum_cb += t
    if max <= sum_cb / sum_b: max = sum_cb / sum_b
    else: break
print max

Submission status: Accepted

Solution code:
N = int(input())
A, B = map(int, input().split())
C = int(input())
D = [None] * N
for i in range(N):
    D[i] = int(input())

D.sort(reverse = True)
numer = C
denom = A
ratio = numer / denom

for i in range(N):
    numer += D[i]
    denom += B
    next_ratio = numer / denom
    if next_ratio <= ratio:
        break
    ratio = next_ratio

print(int(ratio))

Submission status: Accepted

Solution code:
num_choice = int(raw_input())
price=list(map(int,raw_input().split()))
base_cal = int(raw_input())
topping_cal = []
for i in range (num_choice):
	topping_cal.append(int(raw_input()))
topping_cal.sort()
topping_cal.reverse()
average_cal = int(base_cal / price[0])
for i in range (num_choice):
	new_average = int((sum(topping_cal[:i+1]) + base_cal) / (price[0] + price[1] * (i+1)) )
	if new_average >= average_cal:
		average_cal = new_average
	else:
		break
print average_cal

Submission status: Accepted

Solution code:
N = input()
A,B = map(int, raw_input().split())
C = input()
D = [input() for _ in range(N)]
D = sorted(D)[::-1]
price = A
cal = C
ans = cal/price
for d in D:
    cal += d
    price += B
    ans = max(ans, cal/price)
print ans

Submission status: Accepted

Solution code:
n=int(input())
a,b=map(int,input().split())
c=int(input())
d=sorted([int(input()) for _ in range(n)])[::-1]
e=c//a
for x in d:
    a+=b;c+=x
    e=max(e,c//a)
print(e)

Submission status: Accepted

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


"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline
from collections import namedtuple
item = namedtuple('item', ['cal', 'pri'])


def Cond(x, n, items, pizza):
    y = [0] * n
    for i in range(n):
        y[i] = items[i].cal - x * items[i].pri
    y.sort(reverse=True)

    total = pizza.cal - x * pizza.pri
    for i in range(n):
        if y[i] > 0:
            total += y[i]
        else:
            break
    return total >= 0



def main(args):
    # n = 3
    # k = 2
    # items = [item(2, 2), item(5, 3), item(2, 1)]

    N = int(input())
    A, B = map(int, input().split())
    C = int(input())
    toppings = []
    for i in range(N):
        toppings.append(item(int(input()), B))
    pizza = item(C, A)

    lb = 0
    ub = 1e5
    for i in range(100):
        mid = (lb + ub) / 2
        if Cond(mid, N, toppings, pizza):
            lb = mid
        else:
            ub = mid
    print(int(ub))


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=0567
AC
"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple
item = namedtuple('item', ['cal', 'pri'])


def Cond(x, n, items, pizza):
    # y = [0] * n
    # for i in range(n):
    #     y[i] = items[i].cal - x * items[i].pri 
    y = [(items[i].cal - x * items[i].pri) for i in range(n)] #  ?????????????????°???1??????????????????????????????????????¢??????
    y.sort(reverse=True)
    
    total = pizza.cal - x * pizza.pri #  ?????¶?????°????????????????????????????????????
    #  ?????¶?????°??¨??¢??????????????????????????????????¨??????????????????¶(????????????1??????????????????????????????)?????????????????????
    for c in y:
        if c > 0:
            total += c
        else:
            break
    return total >= 0


def main(args):
    # ?????¬ p132 ???????????§???
    N = int(input())
    A, B = map(int, input().split())
    C = int(input())
    toppings = []
    for i in range(N):
        toppings.append(item(int(input()), B))
    pizza = item(C, A)

    lb = 0
    ub = 1e5
    for i in range(100):
        mid = (lb + ub) / 2
        if Cond(mid, N, toppings, pizza):
            lb = mid
        else:
            ub = mid
    print(int(ub))


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

Submission status: Accepted

Solution code:
n = int(input())
a, b = map(int,input().split())
c = int(input())

ds = [int(input()) for i in range(n)]
ds.sort(reverse=True)

ans = c // a
for i in range(n):
  c += ds[i]
  ans = max(c // (a + b * (i + 1)), ans)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A,B=map(int,input().split())
C=int(input())
D=sorted(int(input())for _ in[0]*N)[::-1]
print(max((C+sum(D[:i]))//(A+i*B)for i in range(1,N)))

Submission status: Accepted

Solution code:
N=int(input())
A,B=map(int,input().split())
C=int(input())
D=sorted(int(input())for _ in[0]*N)[::-1]
print(max((C+sum(D[:i]))//(A+i*B)for i in range(N)))

Submission status: Accepted

Solution code:
N=int(input())
A,B=map(int,input().split())
C=int(input())
D=sorted(int(input())for _ in[0]*N)[::-1]
E=C//A
for x in D:A+=B;C+=x;E=max(E,C//A)
print(E)

Submission status: Accepted

Solution code:
N, A, B, C, *D = map(int, open(0).read().split())
D.sort(reverse=1)
ans = C // A
s = 0
for i in range(N):
    s += D[i]
    ans = max(ans, (C + s)//(A + (i+1)*B))
print(ans)

Submission status: Accepted

Solution code:
# AOJ 0567: Best Pizza
# Python3 2018.6.30 bal4u

n = int(input())
a, b = map(int, input().split())
c = int(input())
ans, p = c/a, a
d = [int(input()) for i in range(n)]
d.sort(reverse=True)
for i in range(n):
	t = (c+d[i])/(p+b)
	if t > ans:
		ans = t
		c += d[i]
		p += b
	else: break;
print(int(ans))

Submission status: Accepted

Solution code:
# coding: utf-8
n = int(raw_input()) # トッピングの種類
a, b = map(int, raw_input().split(' ')) # 生地の値段、各トッピングの値段
c = int(raw_input()) # 生地のカロリー

toppings = [int(raw_input()) for x in xrange(n)]

toppings.sort(reverse=True)

part_sum = [0] * (n + 1)
for index, cal in enumerate(toppings):
    part_sum[index + 1] = part_sum[index] + cal

ans = 0

for x in xrange(n + 1):
    p = (c + part_sum[x]) / (a + b * x)
    ans = max(ans, p)

print ans

Submission status: Accepted

Solution code:
N = input()
A, B = map(int, raw_input().split())
C = input()
D = [input() for i in range(N)]
D.sort(reverse=True)
best = 0
for i in range(N):
    topping = D[:i]
    k = len(topping)
    price = A + B * k
    calory = C + sum(topping)
    best = max(best, calory / price)
print best

Submission status: Accepted

Solution code:
n = int(raw_input())
a, b = map(float, raw_input().split(" "))
c = float(raw_input())

toppings = []
for i in range(n):
    toppings.append(float(raw_input()))

toppings.sort(cmp=(lambda x,y:cmp(y,x)))

cal_sum = c
doll_sum = a
for i in range(n):
    if cal_sum/doll_sum < (cal_sum+toppings[i])/(doll_sum+b):
        cal_sum += toppings[i]
        doll_sum += b
    else: break;

print int(cal_sum/doll_sum)

Submission status: Accepted

Solution code:
n = int(input())
c, b = map(int, input().split())
k = int(input())
A = [int(input()) for _ in range(n)]
A.sort(reverse=True)
r = k/c
for i in A:
	k += i
	c += b
	if k/c<=r:
		break
	else:
		r = k/c
print(int(r))

Submission status: Accepted

Solution code:
n = int(input())
p_cost, t_cost = map(int, input().split())
p_cal = int(input())
t_cal = []
for i in range(n) :
    t_cal.append(int(input()))

t_cal.sort(reverse = True)

total_cost = p_cost
total_cal = p_cal
max_total_cal_par_doll = total_cal // total_cost
for i in range(n) :
    total_cost += t_cost
    total_cal += t_cal[i]
    total_cal_par_doll = total_cal // total_cost
    if max_total_cal_par_doll < total_cal // total_cost :
        max_total_cal_par_doll = total_cal // total_cost
        
print(max_total_cal_par_doll)

Submission status: Accepted

Solution code:
#C
N = int(input())
A,B = map(int,input().split())
C = int(input())
T = [int(input()) for i in range(N)]
T.sort(reverse=True)

cal = C
cost = A
for t in T:
    if cal/cost < (cal+t)/(cost+B):
        cal+=t
        cost+=B
    else:
        break
        
print(cal//cost)

Submission status: Accepted

Solution code:
from itertools import accumulate

num = int(input())
a, b = [int(x) for x in input().split()]
p = int(input())

T = []
C = []

for _ in range(num):
    T.append(int(input()))

C.append(int(p/a))
T.sort(reverse=True)

for i,c in enumerate(accumulate(T),start=1):
    C.append( int( (p+c) / (a+i*b)) )

print( sorted(C,reverse=True)[0] )

Submission status: Accepted

Solution code:
n=int(input())
a,b=map(int,input().split())
c=int(input())
d=sorted([int(input()) for _ in [0]*n],reverse=True)
for i in d:
    if c/a<(c+i)/(a+b):
        c+=i
        a+=b
    else:
        break
print(c//a)

Submission status: Accepted

Solution code:
def main():
    t_n = int(input())
    price_a, price_b = map(int, input().split())
    cal_a = int(input())
    t_c = sorted([int(input()) for _ in range(t_n)], reverse=True)

    cpd_a = cal_a / price_a
    cal_sum = cal_a
    price_sum = price_a
    b_sum = 0
    for i in range(t_n):
        b_sum += t_c[i]
        new_cpd_a = (cal_a + b_sum) / (price_a + (i + 1) * price_b)
        if new_cpd_a > cpd_a:
            cal_sum += t_c[i]
            price_sum += price_b
            cpd_a = new_cpd_a

    print(int(cal_sum / price_sum))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a,b=map(int,input().split())
c=int(input())
A=a
C=c
top=[]
for i in range(n):
    top.append(int(input()))
top.sort(reverse=True)
ans=C/A
for i in top:
    C+=i
    A+=b
    now=C/A
    if ans<now:ans=now
    elif ans>=now:break
print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
a, b = map(int, input().split())
c = int(input())

topping = []
for _ in range(n):
    d = int(input())
    topping.append(d)

topping.sort(reverse=True)
ans = c // a
total = c

for i, t in enumerate(topping):
    total += t
    cal = total // (a + (i+1) * b)
    if ans <= cal:
        ans = cal
    else:
        break

print(ans)

Submission status: Runtime Error

Solution code:
A,B = map(int, raw_input().split())
C = input()
D = [input() for _ in range(N)]
D = sorted(D)[::-1]
price = A
cal = C
ans = cal/price
for d in D:
    cal += d
    price += B
    ans = max(ans, cal/price)
print ans