Problem:


Score : 400 points

Problem Statement

You are going out for a walk, when you suddenly encounter N monsters. Each monster has a parameter called health, and the health of the i-th monster is h_i at the moment of encounter. A monster will vanish immediately when its health drops to 0 or below.

Fortunately, you are a skilled magician, capable of causing explosions that damage monsters. In one explosion, you can damage monsters as follows:

Select an alive monster, and cause an explosion centered at that monster. The health of the monster at the center of the explosion will decrease by A, and the health of each of the other monsters will decrease by B. Here, A and B are predetermined parameters, and A > B holds.

At least how many explosions do you need to cause in order to vanish all the monsters?

Constraints

All input values are integers.

1 ≤ N ≤ 10^5

1 ≤ B < A ≤ 10^9

1 ≤ h_i ≤ 10^9

Input

Input is given from Standard Input in the following format:

N A B
h_1
h_2
:
h_N

Output

Print the minimum number of explosions that needs to be caused in order to vanish all the monsters.

Sample Input 1

4 5 3
8
7
4
2

Sample Output 1

2

You can vanish all the monsters in two explosion, as follows:

First, cause an explosion centered at the monster with 8 health. The healths of the four monsters become 3, 4, 1 and -1, respectively, and the last monster vanishes.

Second, cause an explosion centered at the monster with 4 health remaining. The healths of the three remaining monsters become 0, -1 and -2, respectively, and all the monsters are now vanished.

Sample Input 2

2 10 4
20
20

Sample Output 2

4

You need to cause two explosions centered at each monster, for a total of four.

Sample Input 3

5 2 1
900000000
900000000
1000000000
1000000000
1000000000

Sample Output 3

800000000



Sample input:
4 5 3
8
7
4
2


Sample output:
2

Submission status: Accepted

Solution code:
import math


class binarySearch:
    # 添え字「t」によってソート済みリストを二分探索
    def __init__(self, limit, target):
        self.limit = limit
        self.target = target
        self.t = 0

    def condition(self, h, a, b):
        if self.t < 0:
            return False
        count = 0
        for i in range(len(h)):
            if h[i] > b * self.t:
                count += math.ceil((h[i] - b * self.t) / (a - b))
        if count > self.t:
            return False
        else:
            return True

    def search(self, h, a, b):
        low = 0
        high = self.limit
        self.t = int((low + high) / 2)
        while high >= low:
            out = self.condition(h, a, b)
            # print("t:{} _out:{} limit:{}\n".format(t, out, self.limit))
            if not out:
                low = self.t + 1
            else:
                high = self.t - 1
            self.t = int((low + high) / 2)
        # print("low:{} high:{} t:{}".format(low, high, self.t))
        return self.t + 1


def func(a, b, _h):
    _h.sort()
    _h.reverse()
    _sum = 0  # 現在何回以上爆発させることが確定しているか
    aMargin = 0  # _sum回のうちあと何回aを使うことができるか
    for h in _h:
        print("prev cost upper:{}".format(a * aMargin + b * (_sum - aMargin)))
        # まず_sum回で抑える場合にaがいくつ必要か算出
        if h <= a * aMargin + b * (_sum - aMargin):
            # そのうちどれだけaを使わないでいられるか
            h -= b * _sum  # まず必ず減る部分を計算
            if h > 0:
                aMargin -= math.ceil(h / (a - b))  # a が何回必要か
        else:
            # hを0にするのに必要最低限の回数をを算出
            tmpH = h
            tmpH -= a * aMargin + b * (_sum - aMargin)
            extra = math.ceil(tmpH / a)
            _sum += extra
            aMargin += extra
            print("aMargin:{}".format(aMargin))
            # 合計して「_sum」回が最小回数
            # ここで使えるaは「aMargin」回
            # そのうちどれだけaを使わないでいられるか
            h -= b * _sum  # まず必ず減る部分を計算
            aMargin -= math.ceil(h / (a - b))  # a が何回必要か
        print("_sum:{} margin:{}".format(_sum, aMargin))
    return str(_sum)


n, a, b = [int(i) for i in input().split()]
h = [0 for _ in range(n)]
for i in range(n):
    h[i] = int(input())
# print(func(a, b, h))
binary = binarySearch(target=math.ceil(max(h) / a), limit=math.ceil(max(h) / 1))
print(binary.search(h, a, b))
# print("print(func({}, {}, {}))".format(a, b, h))
"""
print("2 vs " + func(5, 3, [8, 7, 4, 2]))
print("4 vs " + func(10, 4, [20, 20]))
print("800000000 vs " + func(2, 1, [900000000, 900000000, 1000000000, 1000000000, 1000000000]))
"""

Submission status: Accepted

Solution code:
import math
import copy

def condition(t, h, a, b):
    count = 0
    for i in range(len(h)):
        if h[i] > b*t:
            count += math.ceil((h[i]-b*t)/(a-b))
    # print("count:{} t:{} _h:{} a:{} b:{}".format(count, t, _h, a, b))
    if count > t:
        return False
    else:
        return True


class binarySearch:
    # 添え字による二分探索
    # 添え字「t」によってソート済みリストを二分探索
    def __init__(self, limit, target):
        self.limit = limit
        self.target = target

    def search(self, h, a, b):
        low = 0
        high = self.limit
        t = int((low + high) / 2)
        while high >= low:
            out = condition(t, h, a, b)
            # print("t:{} _out:{} limit:{}\n".format(t, out, self.limit))
            if not out:
                low = t + 1
            else:
                high = t - 1
            t = int((low + high) / 2)
        for i in range(3):
            if condition(low-i, h, a, b):
                return low-i
        # return low

def func(a, b, _h):
    _h.sort()
    _h.reverse()
    _sum = 0  # 現在何回以上爆発させることが確定しているか
    aMargin = 0  # _sum回のうちあと何回aを使うことができるか
    for h in _h:
        print("prev cost upper:{}".format(a * aMargin + b * (_sum - aMargin)))
        # まず_sum回で抑える場合にaがいくつ必要か算出
        if h <= a * aMargin + b * (_sum - aMargin):
            # そのうちどれだけaを使わないでいられるか
            h -= b * _sum  # まず必ず減る部分を計算
            if h > 0:
                aMargin -= math.ceil(h / (a - b))  # a が何回必要か
        else:
            # hを0にするのに必要最低限の回数をを算出
            tmpH = h
            tmpH -= a * aMargin + b * (_sum - aMargin)
            extra = math.ceil(tmpH / a)
            _sum += extra
            aMargin += extra
            print("aMargin:{}".format(aMargin))
            # 合計して「_sum」回が最小回数
            # ここで使えるaは「aMargin」回
            # そのうちどれだけaを使わないでいられるか
            h -= b * _sum  # まず必ず減る部分を計算
            aMargin -= math.ceil(h / (a - b))  # a が何回必要か
        print("_sum:{} margin:{}".format(_sum, aMargin))
    return str(_sum)


n, a, b = [int(i) for i in input().split()]
h = [0 for _ in range(n)]
for i in range(n):
    h[i] = int(input())
# print(func(a, b, h))
binary = binarySearch(target=math.ceil(max(h)/a), limit=math.ceil(max(h)/1))
print(binary.search(h, a, b))
# print("print(func({}, {}, {}))".format(a, b, h))
"""
print("2 vs " + func(5, 3, [8, 7, 4, 2]))
print("4 vs " + func(10, 4, [20, 20]))
print("800000000 vs " + func(2, 1, [900000000, 900000000, 1000000000, 1000000000, 1000000000]))
"""

Submission status: Accepted

Solution code:
import sys
N,A,B=map(int, raw_input().split()) 
H=[ int(sys.stdin.readline()) for i in range(N) ] 

def func(n , T):
	sa=A-B
	k=0
	for x in T:
		x-=n*B
		if x>0:
			if x%sa==0:
				k+=x/sa
			else:
				k+=(x/sa+1)
		
			if n<k:
				return False
	else:
			return True

l=0
r=10**9
while l!=r:
	m=(r+l)/2
	if func(m,H):
		r=m
	else:
		l=m+1

print l

Submission status: Accepted

Solution code:
import sys
N,A,B=map(int, raw_input().split()) 
H=[ int(sys.stdin.readline()) for i in range(N) ] 

def func(n , T):
	sa=A-B
	k=0
	for x in T:
		x-=n*B
		if x>0:
			if x%sa==0:
				k+=x/sa
			else:
				k+=(x/sa+1)
		
			if n<k:
				return False
	else:
			return True

l=0
r=max(H)/B+1
while l!=r:
	m=(r+l)/2
	if func(m,H):
		r=m
	else:
		l=m+1
	#print l,r,m,func(m,H)

print l

Submission status: Accepted

Solution code:
from math import ceil

N, A, B = map(int, input().split())
H = [int(input()) for i in range(N)]

A -= B  # 爆発は追加ダメージ扱いとする

# にぶたん
ok, ng = 10 ** 9, 0
while abs(ok - ng) > 1:
    X = (ok + ng) // 2

    h = [max(hi - B * X, 0) for hi in H]
    h = [ceil(hi / A) for hi in h]

    if sum(h) <= X:
        ok = X
    else:
        ng = X

print(ok)

Submission status: Accepted

Solution code:
N, A, B = [int(_) for _ in input().split()]
H = [int(input()) for _ in range(N)]


def enough(x):
    return sum([1 + (max(h - B * x, 0) - 1) // (A - B) for h in H]) <= x


ng = 0
ok = 1 + (max(H) - 1) // B

while ok - ng > 1:
    half = (ok + ng) // 2
    if enough(half):
        ok = half
    else:
        ng = half
print(ok)

# https://img.atcoder.jp/arc075/editorial.pdf

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
h_list = [int(input()) for _ in range(N)]
h_max = max(h_list)


def add_attack(t):
    attack = B * t
    for i in range(N):
        h = h_list[i]
        h -= attack
        if h > 0:
            t -= (h + (A - B) - 1) // (A - B)
            if t < 0:
                return False
    return True


t_min = 1
t_max = (h_max + B - 1) // B

while t_min < t_max - 1:
    t_mid = (t_min + t_max) // 2
    if add_attack(t_mid):
        t_max = t_mid
    else:
        t_min = t_mid
print(t_max)

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
h_list = [int(input()) for _ in range(N)]
h_list.sort(reverse=True)
h_max = h_list[0]


def add_attack(t):
    attack = B * t
    for i in range(N):
        h = h_list[i]
        h -= attack
        if h > 0:
            t -= (h + (A - B) - 1) // (A - B)
            if t < 0:
                return False
    return True


t_min = 1
t_max = (h_max + B - 1) // B

while t_min < t_max - 1:
    t_mid = (t_min + t_max) // 2
    if add_attack(t_mid):
        t_max = t_mid
    else:
        t_min = t_mid
print(t_max)

Submission status: Accepted

Solution code:
def judge(h,t,a,b,n):
    counter = 0
    for i in range(n):
        if h[i] > b*t:
            if ((h[i]-b*t)/(a-b))%1 == 0:
                counter += (h[i]-b*t)//(a-b)
            else:
                counter += (h[i]-b*t)//(a-b) + 1
    if counter <= t:
        return True
    else:
        return False

n,a,b = map(int,input().split())
h = []
for i in range(n):
    temp = int(input())
    h.append(temp)

left = 1
right = max(h)//b + 1

while abs(right-left) > 1:
    check = judge(h,(left+right)//2,a,b,n)
    if check:
        right = (left+right)//2
    else:
        left = (left+right)//2

if judge(h,left,a,b,n):
    print(left)
else:
    print(right)

Submission status: Accepted

Solution code:
import math
n, a, b = map(int, input().split())
d = []
for i in range(n):
    d.append(input())
# [d1, d2, d3, ..., dN]
h = [int(m) for m in d]#int型に直す
#print(x)

low = 0
high = math.ceil(max(h)/b)
# t は中央番目の数
t = (low + high) // 2

# 探索の下限のlowが上限のhighになるまで探索
# lowがhighに達すると数は見つからなかっTrueたということ
X = 0
Y = 0
s = 0
while high - low >= 0:
    for j in range(n):
        X += max(0, math.ceil((h[j] - t * b) / (a - b)))
        #Y += max(0, math.ceil((h[j] - (t - 1) * b) / (a - b)))
    if X == t:
        print(t)
        exit()
    elif X < t:
        high = t - 1
        """for j in range(n):
            Y += max(0, math.ceil((h[j] - (t - 1) * b) / (a - b)))"""
    elif X > t:
        low = t + 1
    s = t
    t = (low + high) // 2
    X = 0
    Y = 0
for j in range(n):
  if math.ceil((h[j] - s * b) / (a - b)) > 0:
            Y += math.ceil((h[j] - s * b) / (a - b))
if Y <= s:
  print(s)
else:
  print(s + 1)

Submission status: Accepted

Solution code:
from math import ceil

N, A, B = map(int, input().split())
h = [int(input()) for _ in range(N)]
h = sorted(h)

max(h)

l = 0
r = ceil(max(h) / B) + 1

ans = float('inf')
while l < r:
    t = 0
    cnt = (l + r) // 2
    for i in range(N):
        if h[i] > cnt * B:
            t += ceil((h[i] - cnt * B) / (A - B))
    if t <= cnt:
        ans = min(ans, cnt)
        r = cnt
    else:
        l = cnt + 1

print(ans)

Submission status: Accepted

Solution code:
import math
n,a,b=map(int,input().split())
h=[]
for i in range(n):
    h.append(int(input()))
def sten(t):
    dh=[]
    for i in range(n):
        if h[i]-t*b>0:
            dh.append(h[i]-t*b)
    aan=0
    for i in range(len(dh)):
        aan+=math.ceil(dh[i]/(a-b))
    if aan<=t:
        return True
    else:
        return False

left = 0
right = int(1e9)
while left < right:
    center = (left + right) // 2
    if sten(center):
        right = center
    else:
        left = center + 1
print(left)

Submission status: Accepted

Solution code:
import math
N,A,B=map(int,input().split())
H=[int(input()) for i in range(N)]
left=1
right=10**10
while left!=right:
  x=(left+right)//2
  S=0
  for i in range(N):
    if H[i]-B*x>=0:
      S+=math.ceil((H[i]-B*x)/(A-B))
  if S<=x:
      right=x
  else:
      left=x+1
print(left)

Submission status: Accepted

Solution code:
import math

N,A,B=list(map(int,input().split()))
arr=[]
h_sum=0
for i in range(N):
    h=int(input())
    arr.append(h)
    h_sum+=h

max_=max(arr)//B+1
min_=h_sum//(A+B*(N-1))

d=A-B

while min_!=max_:
    mid=(max_+min_)//2
    
    sum_=0
    for x in arr:
        y=(x-mid*B)
        if y<=0:
            continue
        sum_+=math.ceil(y/d)
        
    if sum_<=mid:
        max_=mid
    else:
        min_=mid+1

print(min_)

Submission status: Accepted

Solution code:
import math        
    
N,A,B=list(map(int,input().split()))
arr=[]

for i in range(N):
    arr.append(int(input()))

max_=max(arr)//B+1
min_=min(arr)//A

d=A-B

while min_!=max_:
    mid=(max_+min_)//2
    
    sum_=0
    for x in arr:
        y=(x-mid*B)
        if y<=0:
            continue
        sum_+=math.ceil(y/d)
        
    if sum_<=mid:
        max_=mid
    else:
        min_=mid+1

print(min_)

Submission status: Accepted

Solution code:
import math
"""
def search(min_,max_,A,B,arr):
#    print(min_,max_)
    if min_==max_:
        return min_
    mid=(max_+min_)//2
    
    tmp=arr-mid*B
    
    if len(tmp)==0:
        return search(min_,mid,A,B,arr)
    
    tmp=map(lambda x:math.ceil(x/(A-B)),tmp)
    sum_=sum(list(tmp))
    if sum_<=mid:
        return search(min_,mid,A,B,arr)
    else:
        return search(mid+1,max_,A,B,arr)

    while True:
        if k<0:
            if mid==min_:
                return max_
            else:
                #failure
                return search(mid,max_,A,B,arr[:L])
        elif len(tmp)==0:
            #success
            return search(min_,mid,A,B,arr)
        x=-tmp[0]
        tmp=np.delete(tmp,0)
        k-=x//(A-B)+(x%(A-B)>0)
"""
        
    
N,A,B=list(map(int,input().split()))
arr=[]

for i in range(N):
    arr.append(int(input()))

max_=max(arr)//B+1
min_=min(arr)//A

d=A-B

while min_!=max_:
    mid=(max_+min_)//2
    
    sum_=0
    for x in arr:
        sum_+=max(0,math.ceil((x-mid*B)/d))
        
    if sum_<=mid:
        max_=mid
    else:
        min_=mid+1

print(min_)

Submission status: Accepted

Solution code:
import sys
import math

# 再帰
def solve_rec(n, a, b, h_lst, ans_min, ans_max):
    if ans_min == ans_max:
        return ans_min

    if ans_min > ans_max:
        return -1

    pivot = (ans_min + ans_max) // 2
    # print("try: {}".format(pivot))
    is_beatable = beatable(a, b, h_lst, pivot)

    if is_beatable:
        # print("beatable: {} {}".format(ans_min, ans_max))
        return solve_rec(n, a, b, h_lst, ans_min, pivot)
    else:
        # print("not beatable: {} {}".format(ans_min, ans_max))
        return solve_rec(n, a, b, h_lst, pivot+1, ans_max)

def beatable(a, b, h_lst, pivot):
    # まずBずつ削る
    living = [ h - b * pivot for h in h_lst if h > b * pivot ]
    # print(living)

    # 生き残ったものを1回ずつ(A-B)ダメージずつ与えていくときに、必要な回数
    c = sum([ math.ceil(1.0 * h / (a-b)) for h in living ])
    
    return c <= pivot

def solve(n, a, b, h_lst):
    h_max = max(h_lst)
    ans_min = 0
    ans_max = h_max // b + 1

    return solve_rec(n, a, b, h_lst, ans_min, ans_max)

def main():
    line = sys.stdin.readline()
    lst = line.split()
    n = int(lst[0])
    a = int(lst[1])
    b = int(lst[2])

    h_lst = []
    for i in range(n):
        line = sys.stdin.readline()
        h = int(line)
        h_lst.append(h)
        

    ans = solve(n, a, b, h_lst)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil
N, A, B = map(int, input().split())
H = [int(input()) for i in range(N)]

A = A - B
ng, ok = 0, 10 ** 9 + 1
while abs(ok - ng) > 1:
    X = (ng + ok) // 2
    H_damaged = [h - B * X for h in H]
    need = sum([max(ceil(h / A), 0) for h in H_damaged])

    if need <= X:
        ok = X
    else:
        ng = X

print(ok)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def is_cond(T, A, B, h):

    s = 0
    for i in range(len(h)):
        h_new = h[i] - B*T
        if h_new > 0:
            s += h_new / (A - B) + (0 if h_new % (A - B) == 0 else 1)

    return s <= T

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, A, B] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2])]
    h = []
    for i in range(N):
        input_raw = read_func().strip().split()
        h.append(long(input_raw[0]))
    
    l = 0L
    r = max(h)/B + 1
    while(1):
        #print l r
        if abs(l - r) <= 1:
            print r
            break
        T = (l + r)/2
        if is_cond(T, A, B, h) == True:
            r = T
        else:
            l = T


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
h = []

for i in range(N):
    h.append(int(input()))

def bool(n, h):
    h.sort()
    damage = n * B
    hx = list(map(lambda x: x - damage, h))
    count = 0
    for i in range(len(hx)):
        count += max(0, 1 + (hx[i]-1) // (A - B))
    if count > n:
        return False
    else:
        return True
start = 0
end = 10000000000
while end - start > 1:
    mean = (start + end)//2
    if bool(mean, h):
        end = mean
    else:
        start = mean

print(end)

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
H = [int(input()) for i in range(N)]
H.sort()
from math import ceil
def KnockOut(t):
    base = B*t
    for i in range(N):
        h = H[i]
        h -= base
        if h > 0:
            t -= ceil(h/(A-B))
            if t < 0:
                return False
    return True
l = 0
r = ceil(max(H)/B)
while l != r-1:
    t = int((l+r)/2)
    if KnockOut(t):
        r = t
    else:
        l = t
print(r)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
h=[int(input()) for _ in range(n)]

def judge(t):
    res=0
    for x in h:
        if x-b*t>0:
            res+=-(-(x-b*t)//(a-b))
    return res<=t
low=0
high=10**9+1
while high-low>1:
    mid=(low+high)//2
    if judge(mid):
        high=mid
    else:
        low=mid
print(high)

Submission status: Accepted

Solution code:
def roof(a, b):
    if a%b == 0:
        return a//b
    else:
        return a//b + 1

N, A, B = map(int, input().split())
H = [int(input()) for i in range(N)]

low, high = 0, 10**9
while high - low > 1:
    mid = (low + high)//2
    count = 0
    for i in range(N):
        if H[i] - (B * mid) > 0:
            count += roof(H[i]-(B*mid), A-B)
    if count > mid:
        low = mid
    else:
        high = mid
print(high)

Submission status: Accepted

Solution code:
from math import ceil
N, A, B = map(int,input().split())
h = []
for k in range(N):
    h.append(int(input()))

def check(t):
    s = t
    for k in range(N):
        if h[k] > B*t:
            s -= ceil((h[k]-B*t)/(A-B))
        if s < 0:
            return False
    return True

lo = 0
hi = max(h)+1

while hi - lo > 1:
    mid = (hi+lo)//2
    if check(mid):
        hi = mid
    else:
        lo = mid

print(hi)

Submission status: Accepted

Solution code:
import math

def f(h, a, b, t):
    y = 0
    for hi in h:
        if hi-b*t <= 0:
            break
        else:
            y += math.ceil((hi-b*t)/(a-b))
    if y <= t:
        return True
    else:
        return False

n, a, b = list(map(int, input().split()))
h = []
for _ in range(n):
    h.append(int(input()))
h.sort(reverse=True)

low = 0
high = math.ceil(h[0]/b)

while True:
    m = (low+high)//2
    if f(h,a,b,m):
        high = m
    else:
        low = m
    if low +1 == high:
        break

print(high)

Submission status: Accepted

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

n, a, b = map(int, input().split())
H = [int(input()) for _ in range(n)]


def ok(t):
    count = 0
    for h in H:
        if h - b*t > 0:
            count += -(-(h - b*t) // (a - b))
    return count <= t


lo = 0
hi = 10**9+1
while hi - lo > 1:
    mid = (lo + hi) // 2
    if ok(mid):
        hi = mid
    else:
        lo = mid
print(hi)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
h = [int(input()) for i in range(n)]

left = 0
right = 10**10
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    count = 0
    for i in range(n):
        if h[i] - mid * b > 0:
            if (h[i] - mid * b) % (a - b) == 0:
                count += (h[i] - mid * b) // (a - b)
            else:
                count += (h[i] - mid * b) // (a - b) + 1
    if mid - count >= 0:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
lis = [int(input()) for i in range(n)]
more = a-b

def tansaku(x):
  cou = 0
  normal = b * x
  for hp in lis:
    r = hp -normal
    if r <= 0:continue
    cou += r // more
    
    if r % more != 0:
      cou += 1
  return cou <= x

left = 1
right = max(lis)
while right - left > 1:
  mid = (right + left)//2
  if tansaku(mid):
    right = mid
  else:
    left = mid
print(right)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def mera(n: int, hp:list, a:int, b:int) -> bool:
    hp = [hpi - n*b for hpi in hp]
    
    center = 0
    for hpi in hp:
        if hpi <= 0:
            continue
        else:
            center += (hpi//(a-b) + bool(hpi%(a-b)))

    if center > n:
        return False
    else:
        return True
    

n,a,b = li()
hp = [ni() for _ in range(n)]

# 二分探索
low = 0
high = max(hp)//b+1

while high - low > 1:
    mid = (high+low) // 2
    if mera(mid,hp,a,b):
        high = mid
    else:
        low = mid
        

print(high)

Submission status: Accepted

Solution code:
from math import ceil
N, A, B = map(int, input().split())
H = sorted([int(input()) for i in range(N)])
C = A - B

lo, hi = -1, 10**9
while hi - lo > 1:
    X = (hi + lo) // 2
    H2 = [max(0, h - (X * B)) for h in H]
    need = sum([ceil(h / C) for h in H2])
    if need > X:
        lo = X
    else:
        hi = X

print(hi)

Submission status: Accepted

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

def defeat(atk):
    if atk*B >= hs[0]:
        return True
    count = 0
    for h in hs:
        if h <= atk*B: break
        rem = h - atk*B
        count += -(-rem//(A-B))
        if count > atk:
            return False
    return True

ok = 10**9
ng = 0
while ok - ng > 1:
    m = (ok+ng)//2
    if defeat(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def ok(n, A, B, H):
    num = 0
    for h in H:
        r = h - n * B
        if r > 0:
            num += ceil(r, (A - B))
    return num <= n


def main():
    N, A, B = map(int, input().split())
    H = sorted([int(input()) for _ in range(N)])

    low, high = 0, 10 ** 10
    ans = 0
    while high - low > 1:
        middle = (low + high) // 2
        if ok(middle, A, B, H):
            ans = middle
            high = middle
        else:
            low = middle

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, A, B = map( int, input().split())
hmax = 0
H = [ int( input()) for _ in range(N)]
hmax = max(H)
L = 0
R = hmax//B + 1
add = A-B
while R-L != 1:#L != R:
    now = (L+R)//2
    need = 0
    for i in range(N):
        r = H[i] - now*B
        if r > 0:
            need += (r-1)//add+1
    if need <= now:#うまくいくとき
        R = now
    else:#うまくいかないとき
        L = now#+1#うまく行かないので+1している．これがないと無限ループが発生する。
print(R)

Submission status: Accepted

Solution code:
N, A, B = map( int, input().split())
hmax = 0
H = [ int( input()) for _ in range(N)]
#hmax = max(H)
L = 0
R = 10**9+1#hmax//B + 1
add = A-B
while L != R:
    now = (L+R)//2
    need = 0
    for i in range(N):
        r = H[i] - now*B
        if r > 0:
            need += (r-1)//add+1
    if need <= now:#うまくいくとき
        R = now
    else:#うまくいかないとき
        L = now+1#うまく行かないので+1している．これがないと無限ループが発生する。
print(L)

Submission status: Accepted

Solution code:
N, A, B = map( int, input().split())
hmax = 0
H = [ int( input()) for _ in range(N)]
hmax = max(H)
L = 0
R = hmax//B + 1
add = A-B
while L != R:
    now = (L+R)//2
    need = 0
    for i in range(N):
        r = H[i] - now*B
        if r > 0:
            need += (r-1)//add+1
    if need <= now:#うまくいくとき
        R = now
    else:#うまくいかないとき
        L = now+1#うまく行かないので+1している．これがないと無限ループが発生する。
print(L)

Submission status: Accepted

Solution code:
N, A, B = map( int, input().split())
H = [0]*N
hmax = 0
for i in range(N):
    h = int( input())
    H[i] = h
hmax = max(H)
L = 0
R = hmax//B + 1
add = A-B
while L != R:
    now = (L+R)//2
    need = 0
    for i in range(N):
        r = H[i] - now*B
        if r > 0:
            need += (r-1)//add+1
    if need <= now:#うまくいくとき
        R = now
    else:#うまくいかないとき
        L = now+1#うまく行かないので+1している．これがないと無限ループが発生する。
print(L)

Submission status: Accepted

Solution code:
N, A, B = map( int, input().split())
H = [0]*N
hmax = 0
for i in range(N):
    h = int( input())
    H[i] = h
hmax = max(H)
L = 0
R = hmax//B + 1
add = A-B
while L != R:
    now = (L+R)//2
    need = 0
    for i in range(N):
        if H[i] > now*B:
            need += (H[i]-1-now*B)//add + 1
    if need <= now:#うまくいくとき
        R = now
    else:#うまくいかないとき
        L = now+1#うまく行かないので+1している．これがないと無限ループが発生する。
print(L)

Submission status: Accepted

Solution code:
N, A, B = map( int, input().split())
H = [0]*N
hmax = 0
for i in range(N):
    h = int( input())
    H[i] = h
    hmax = max( h, hmax)

L = 0
R = hmax//B + 1
add = A-B
while L != R:
    now = (L+R)//2
    need = 0
    for i in range(N):
        if H[i] > now*B:
            need += (H[i]-1-now*B)//add + 1
    if need <= now:#うまくいくとき
        R = now
    else:#うまくいかないとき
        L = now+1#うまく行かないので+1している．これがないと無限ループが発生する。
print(L)

Submission status: Accepted

Solution code:
N, A, B = map( int, input().split())
H = [0]*N
hmax = 0
for i in range(N):
    h = int( input())
    H[i] = h
    hmax = max( h, hmax)

L = 0
R = hmax//B + 1
add = A-B
while L != R:
    now = (L+R)//2
    need = 0
    for i in range(N):
        if H[i] > now*B:
            need += (H[i]-1-now*B)//add + 1
    if need <= now:
        R = now
    else:
        L = now+1
print(L)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, A, B = map(int, input().split())
h = [int(input()) for _ in range(N)]


def is_OK(x):
    cnt = 0
    for hi in h:
        hi -= B * x
        if hi > 0:
            if hi % (A - B) == 0:
                cnt += hi // (A - B)
            else:
                cnt += hi // (A - B) + 1
    return cnt <= x


left = 0
right = sum(h) // A + N
while right - left > 1:
    mid = (left + right) // 2
    if is_OK(mid):
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
h=[int(input()) for _ in [0]*n]
f=lambda n:lambda x:x-b*n

def calc(n):
  g=f(n)
  k=lambda x:1+x//(a-b) if x%(a-b) else x//(a-b)
  o=filter(lambda x:x>0,map(g,h))
  *p,=map(k,o)
  if not p:
    return True
  else:
    return sum(p)<=n

l,r=0,max(h)
while r-l>1:
  m=(r+l)//2
  if calc(m):
    r=m
  else:
    l=m
print(r)

Submission status: Accepted

Solution code:
import math
n,a,b = map(int,input().split())
h = [int(input()) for i in range(n)]
def cheak(x):
  kiso = b*x
  kai = 0
  for i in h:
    if kiso < i:
      kai += math.ceil((i-kiso)/(a-b))
  if kai > x:
    return 0
  else:
    return 1
dai = max(h)
syo = 0
while True:
  if dai-syo == 1:
    break
  kon = (dai+syo)//2
  c = cheak(kon)
  if c == 1:
    dai = kon
  else:
    syo = kon
print(dai)

Submission status: Accepted

Solution code:
#ab = [tuple(map(int, input().split())) for _ in range(n)]
import math
n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()

def check(j):
    cnt = 0
    for i in range(n):
        tmp = math.ceil((h[i] - b*j) / (a-b))
        if tmp <= 0:
            pass
        else:
            cnt += tmp
    if cnt <= j:
        return True
    else:
        return False


def bs(l,r):
    while l != r:
        m = (l+r)//2
        if check(m):
            r = m
        else:
            l = m+1
    return l

print(bs(0, 10**9))

Submission status: Accepted

Solution code:
import math
N, A, B = map(int, input().split())
H = [0] * N
maxh = 0
for i in range(N):
  h = int(input())
  H[i] = h
  maxh = max(h, maxh)
lower = 0
upper = math.ceil(maxh / B)
def search(upper, lower):
  if lower + 1 == upper:
    return upper
  else:
    mid = (upper + lower) // 2
    _H = [h - mid * B for h in H]
    cnt = 0
    for h in _H:
      if h > 0:
        cnt += math.ceil(h / (A - B))
    if cnt <= mid:
      return search(mid, lower)
    else:
      return search(upper, mid)
print(search(upper, lower))

Submission status: Accepted

Solution code:
import sys,math

N,A,B=map(int,input().split())
H = [0] * N
H = [int(input()) for i in range(N)]
 
maxH = max(H)
L=-1
R=math.ceil(maxH / B)

while R-L>1:
    MID=(L+R)//2
    if sum(math.ceil(max(h-B*MID,0)/(A-B))for h in H)>MID:
        L=MID
    else:
        R=MID

print(R)

Submission status: Accepted

Solution code:
import math

N,A,B=map(int,input().split())
H = [0] * N
H = [int(input()) for i in range(N)]

maxH = max(H)
L=-1
R=math.ceil(maxH / B)

def binary_search(D,U):
    MID=(D+U)//2
    if(MID==D):
        print(U)
    else:
        if sum(math.ceil(max(h-B*MID,0)/(A-B))for h in H)<=MID:
            binary_search(D,MID)
        else:
            binary_search(MID,U)


binary_search(L,R)