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:
def binary_search(h, left, right, a,b):
    d = a-b
    while left + 1 < right:
        k = (left+right)//2
        cost = 0
        for i in h:
            tmp = i - k * b
            if tmp <= 0:
                continue
            cost += (tmp + d - 1) // d
        # print(left,right, k, cost)
        if cost > k:
            left = k
        else:
            right = k
    return right


n,a,b = map(int,input().split())
h = []
cnt = 0
for _ in range(n):
    i = int(input())
    h.append(i)
    cnt += (i+a-1)//a
print(binary_search(h, -1, cnt+1,a,b))

Submission status: Accepted

Solution code:
from math import ceil
n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort(reverse=True)
ok,ng=10**9,0
while ok-ng>1:
  mid=(ok+ng)//2
  damage=mid*b
  addition=mid
  flag=True
  for i in range(n):
    if h[i]<=damage:
      continue
    else:
      if addition>=ceil((h[i]-damage)/(a-b)):
        addition-=ceil((h[i]-damage)/(a-b))
      else:
        addition-=ceil((h[i]-damage)/(a-b))
        flag=False
        break
  if flag:
    ok=mid
  else:
    ng=mid
print(ok)

Submission status: Accepted

Solution code:
n,a,b = map(int, input().split( ))
h = [int(input()) for _ in range(n)]
mx = 10**10
mn = 0
#2分探索
while mx-mn>1:
    md = (mx+mn)//2
    h2 = [h[i]-md*b for i in range(n)]
    
    tmp = 0
    for i in range(n):
        if h2[i]>0:
            tmp += (h2[i]+(a-b)-1)//(a-b)
    if tmp<=md:
        mx = md
    else:
        mn = md

print(mx)

Submission status: Accepted

Solution code:
u = 10**9
d = 0
N,A,B = map(int,input().split())
s = A - B
H = []
import math
for i in range(N):
    h = int(input())
    H.append(h)
for i in range(30):
    x = (u+d)//2
    a = 0
    for j in range(N):
        h = H[j]
        h -= B*x
        if h > 0:
            a += math.ceil(h/s)
    if a > x:
        d = x
    else:
        u = x
print(u)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
h=[int(input())for _ in range(n)]
ok=10**9
ng=0
while ng+1!=ok:
  mid=(ok+ng)//2
  s=0
  for i in h:
    j=max(i-mid*b,0)
    s+=0--j//(a-b)
  if s>mid:ng=mid
  else:ok=mid
print(ok)

Submission status: Accepted

Solution code:
import math
N,A,B = map(int,input().split())
H = [int(input()) for _ in range(N)]
low = sum(H)//((N-1)*B+A)-1
high = max(H)//B+1
while high-low>1:
    mid = (high+low)//2
    cnt = 0
    for i in range(N):
        cnt += math.ceil(max(H[i]-mid*B,0)/(A-B))
    if cnt<=mid:
        high = mid
    else:
        low = mid
print(high)

Submission status: Accepted

Solution code:
N, A, B, *H = map(int, open(0).read().split())

def is_ok(K):
    return sum(max(0, -(-(h - B * K) // (A - B))) for h in H) <= K

ng, ok = 0, 10 ** 9
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
def bisect(f, ok, err):
    while abs(ok - err) > 1:
        m = (ok + err) // 2
        if f(m):
            ok = m
        else:
            err = m
    return ok

def main():
    N, A, B = map(int, input().split())
    H = [int(input()) for _ in range(N)]
    A -= B
    def f(n):
        return sum((max(0,h-B*n)+A-1)//A for h in H) <= n
    print(bisect(f, 10**9+1, 0))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

l = 0
r = 10 ** 18

while r - l > 1:
  m = (r + l) // 2
  li = [h - b * m for h in H]
  cnt = sum([(i - 1) // (a - b) + 1 if i > 0 else 0 for i in li])
  if cnt <= m:
    r = m
  else:
    l = m
print(r)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, A, B = MAP()
h = [INT() for _ in range(N)]

ng = 0
ok = ceil(max(h)/B)

def is_ok(x):
    h_copy = h[:]
    for i in range(N):
        h_copy[i] -= B*x
    cnt = 0
    for i in range(N):
        cnt += max(0, ceil(h_copy[i]/(A-B)))
    return cnt <= x


while ng+1 != ok:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

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)]
h.sort(reverse=True)
left = 0
right = 10**10
while left < right:
    mid = (left + right) // 2
    remaining = mid
    ok = True
    for health in h:
        x = (health-B*mid+A-B-1) // (A-B)
        remaining -= x
        if remaining < 0:
            ok = False
            break
    if ok:
        right = mid
    else:
        left = mid + 1
print(right)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,a,b = map(int,input().split())
hls = [int(input()) for i in range(n)]
l = 0
r = sum(hls)
while l<r:
  x = (l+r)//2
  cnt = 0
  for hp in hls:
    if hp-x*b>0:
      cnt += (hp-x*b+(a-b)-1)//(a-b)
  if cnt>x:
    l = x+1
  elif cnt<x:
    r = x
  else:
    ans = x
    break
if l == r:
  ans = l
print(ans)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
hls = [int(input()) for i in range(n)]
l = 0
r = 10**15
while l<r:
  x = (l+r)//2
  cnt = 0
  for hp in hls:
    if hp-x*b>0:
      cnt += (hp-x*b+(a-b)-1)//(a-b)
  if cnt>x:
    l = x+1
  elif cnt<x:
    r = x
  else:
    ans = x
    break
if l == r:
  ans = l
print(ans)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
H = [int(input()) for _ in range(n)]
c = a - b
def is_can(x):
  s = 0
  d = b*x
  for h in H:
    s += max(0, -(-(h-d) // c))
  if s <= x:
    return True
  return False

ng = 0
ok = -(-max(H)//b)
while ok - ng > 1:
  m = (ok+ng)//2
  if is_can(m):
    ok = m
  else:
    ng = m
print(ok)

Submission status: Accepted

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

start=0
end=10**9
import math

for _ in range(30):
    sub=0
    judge=(start+end)/2
    for some in lists:
        sub+=max(0,math.ceil((some-b*math.floor(judge))/(a-b)))

    if sub<judge:
        start=start
        end=judge
    elif sub>=judge:
        start=judge
        end=end
print(math.floor(start)+1)

Submission status: Accepted

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


def explode(x):
    global n
    c=0
    for i in range(n):
        if h[i]-x*b>0:
            c+=math.ceil((h[i]-x*b)/(a-b))
    return c<=x

l,r=1,10**9
while l+1<r:
    k=(l+r)//2
    if explode(k):
        r=k
    else:
        l=k

print(l if explode(l) else r)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

def check(m):
    b = B * m
    cnt = 0
    for h in H:
        # 全体攻撃
        h -= b
        if h > 0:
            # 単体攻撃
            cnt += ceil(h, A)
    # 必要な単体攻撃の回数がm以下ならOK
    return cnt <= m

N, A, B = MAP()
H = LIST(N)
# Aを単体攻撃、Bを全体攻撃とする
A -= B

# 二分探索
res = bisearch_min(0, 10**9, check)
print(res)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

def check(m):
    # 全体攻撃
    b = B * m
    H2 = [h-b for h in H]
    # 単体攻撃
    cnt = 0
    for h in H2:
        if h > 0:
            cnt += ceil(h, A)
    # 必要な単体攻撃の回数がm以下ならOK
    return cnt <= m

N, A, B = MAP()
H = LIST(N)
# Aを単体攻撃、Bを全体攻撃とする
A -= B

# 二分探索
res = bisearch_min(0, 10**9, check)
print(res)

Submission status: Accepted

Solution code:
import math

N,A,B = map(int, input().split())

H = [int(input()) for _ in range(N)]
H.sort(reverse=True)

# mid回の攻撃で全撃破できるか確認。
hi = math.ceil(H[0] / B)
lo = 1


while hi - lo > 1:
    can_defeat_all_enemies = True
    mid = (hi+lo) // 2
    cnt_extra_attack = 0

    for i in range(N):
        if H[i] > mid * B:
            cnt_extra_attack += math.ceil((H[i] - mid * B) / (A - B))
        # 降順に並べてあるので、あるモンスターで追加攻撃が必要なければそれ以降も必要ない
        else:
            break
    
    # mid以下しか追加攻撃が必要ないので倒しきれる
    if cnt_extra_attack <= mid:
        hi = mid
    else:
        lo = mid

print(hi)

Submission status: Accepted

Solution code:
import math

N,A,B = map(int, input().split())

H = [int(input()) for _ in range(N)]
H.sort(reverse=True)

# mid回の攻撃で全撃破できるか確認。
hi = H[0]
lo = 1


while hi - lo > 1:
    can_defeat_all_enemies = True
    mid = (hi+lo) // 2
    cnt_extra_attack = 0

    for i in range(N):
        if H[i] > mid * B:
            cnt_extra_attack += math.ceil((H[i] - mid * B) / (A - B))
        # 降順に並べてあるので、あるモンスターで追加攻撃が必要なければそれ以降も必要ない
        else:
            break
    
    # mid以下しか追加攻撃が必要ないので倒しきれる
    if cnt_extra_attack <= mid:
        hi = mid
    else:
        lo = mid

print(hi)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def ok(m):
        an=m
        for h in hh:
            d=h-b*m
            if d>0:
                an-=(d+a-b-1)//(a-b)
            if an<0:return False
        return True

    n,a,b=MI()
    hh=[int(input()) for _ in range(n)]
    mx=max(hh)
    l=mx//a-1
    r=mx//b+2
    while l+1<r:
        m=(l+r)//2
        if ok(m):r=m
        else:l=m
    print(r)

main()

Submission status: Accepted

Solution code:
# 方針はX回で出来るかどうかの二分探索
N, A, B = map(int, input().split())
demon_health = [0 for i in range(N)]
for i in range(N):
    demon_health[i] = int(input())

high = int(1e10)
low = 0
mid = 0
ad_attack = B - A

while low < high:
    big_magic = 0
    mid = (high + low) // 2
    # mid*Bを使ってB-Aが何回必要かみたいな
    for i in range(N):
        big_magic += max((demon_health[i] - B * mid + (A - B - 1)) // (A - B), 0)
        # print(big_magic)
    if big_magic > mid:
        # cannot
        low = mid + 1
    else:
        high = mid
    # print("high, low -> " + str(high) + " " + str(low))

print(low)

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, a, b = list(map(int, input().rstrip('\n').split()))
    h = [int(input().rstrip('\n')) for _ in range(n)]
    cor_v = 10 ** 16
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n):
            hp = h[i] - bin_v * b
            if hp > 0:
                cost += (hp + (a - b) - 1) // (a - b)
        #costが制約を満たすか
        if cost <= bin_v:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def check(M):
    global A,B,Data
    plus = 0
    for d in Data:
        left = d - B*M 
        if left > 0:
            q,mod = divmod(left,A-B)
            plus += q
            if mod > 0:
                plus += 1
    return plus <= M

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

min1 = 0
max1 = 10**10

while max1 - min1 > 1:
    mid = (min1 + max1) // 2
    b = check(mid)
    if b == True:
        max1 = mid
    else:
        min1 = mid

print(max1)

Submission status: Accepted

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

D = A - B

L = -1
R = 10 ** 9

while L + 1 < R:
  M = (L + R) // 2
  
  cnt = 0
  for h in H:
    rest = h - M * B
    if rest > 0:
      cnt += - (- rest // D)
  if M >= cnt:
    R = M
  else:
    L = M
print(R)

Submission status: Accepted

Solution code:
import sys
import numpy as np

n, a, b = map(int, sys.stdin.readline().split())
h = np.array(sys.stdin.read().split(), dtype=np.int64)
r = a - b

def can_vanish_all(c):
    res = np.copy(h)
    res = np.maximum(res - b * c, 0)
    res = (res + r - 1) // r
    return np.sum(res) <= c

def main():
    lo = 0 # 不可能最大
    hi = 10**9+1 # 可能最小
    while lo + 1 < hi:
        cnt = (lo + hi) // 2
        if can_vanish_all(cnt):
            hi = cnt
        else:
            lo = cnt
    
    return hi

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

ub = 10**9
lb = 0
while True:
    if ub == lb:
        break
    target = (ub + lb) // 2
    need = 0
    for h in hl:
        rest = h - target * b
        need += max(math.ceil(rest / (a-b)), 0)
    if need <= target:
        ub = target
    else:
        lb = target + 1
print(lb)

Submission status: Accepted

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

N, A, B = list(map(int, input().split()))
C = A-B
H = [int(input()) for _ in range(N)]

def check(K):
  s = 0
  D = K*B
  for h in H: s += max(0, (h-D+C-1)//C)
  return s<=K

max_NG = 0
min_OK = 10**10
while min_OK - max_NG > 1:
  tgt = (max_NG+min_OK)//2
  if check(tgt):
    min_OK = tgt
  else:
    max_NG = tgt

print(min_OK)

Submission status: Accepted

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

OK = max(H)//B+1
NG = 0

ans = OK
while OK-NG > 1:
    mid = (OK+NG)//2  # 試行する値
    cnt = 0

    for h in H:
        if h > mid*B:
            cnt += math.ceil((h-mid*B)/(A-B))

    if cnt <= mid:
        OK = mid
    else:
        NG = mid

print(OK)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,A,B = II()
h = Line(N,1)

left = -1
right = 10**9

while abs(right-left)>1:
    mid = (right+left)//2
    counter = 0
    for i in range(N):
        if h[i]>mid*B:
            counter += math.ceil((h[i]-mid*B)/(A-B))
    if counter<=mid:
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read

N, A, B, *h = map(int, read().split())

h = np.array(h, np.int64)

# 2部探索する。n回の爆発で魔物をすべて倒せるか否や
l = 0
r = max(h) // B + 2
a = A - B
while l + 1 < r:
    mid = (l + r) // 2
    w = B * mid
    tmp = h - w
    tmp = tmp[tmp > 0]
    tmp = tmp // a + np.minimum(tmp % a, 1)
    if tmp.sum() <= mid:
        r = mid
    else:
        l = mid

print(r)

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read

N, A, B, *h = map(int, read().split())

h = np.array(h, np.int64)

# 2部探索する。n回の爆発で魔物をすべて倒せるか否や
l = 0
r = (max(h) // B) * N
a = A - B
while l + 1 < r:
    mid = (l + r) // 2
    w = B * mid
    tmp = h - w
    tmp = tmp[tmp > 0]
    tmp = tmp // a + np.minimum(tmp % a, 1)
    if tmp.sum() <= mid:
        r = mid
    else:
        l = mid

print(r)

Submission status: Accepted

Solution code:
_,a,b,*H=map(int,open(0).read().split())
l,r=0,10**9
while r-l>1:
	m=(l+r)//2
	if-sum(min(0,(h-m*b)//(b-a))for h in H)>m:l=m
	else:r=m
print(r)

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
H = [int(input()) for _ in range(N)]
C = A - B
l, r = 0, 1<<30
while r - l > 1:
    m = (l + r) // 2
    if sum([max((h - B * m + C - 1) // C, 0) for h in H]) <= m:
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
Aadd=A-B
H=[0]*N
for i in range(N):
  H[i]=int(input())
MAXV=max(H)//B+(max(H)%B>0)
ng=-1
ok=MAXV+1

def isOK(n):
  Anum=0
  Bdamage=n*B
  for i in range(len(H)):
    rest=H[i]-Bdamage
    if rest>0:
      Anum+=rest//Aadd+(rest%Aadd>0)
  if Anum<=n:
    return True
  return False
        
while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOK(mid):
    ok=mid
  else:
    ng=mid
    
print(ok)

Submission status: Accepted

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

import math

def C(d):
    sum = 0
    for i in range(n):
        sum += math.ceil(max(h[i] - b * d, 0) / (a - b))
    return sum <= d

lb = -1
ub = 10 ** 9 + 1
while (ub - lb) > 1:
    mid = (lb + ub) // 2
    if C(mid):
        ub = mid
    else:
        lb = mid
print(ub)

Submission status: Accepted

Solution code:
import math
n, a, b = map(int, input().split())
h = []
spread = b
attack = a - b
count = 0
for i in range(n):
    h.append(int(input()))
h.sort()
h.reverse()
def binary_search(left, right):
    if right - left <= 1:
        return right
    middle = (right + left)//2
    count = 0
    for i in range(n):
        if h[i] - (middle * spread) <= 0:
            break
        else:
            count += math.ceil((h[i] - (middle * spread)) / attack)
    if count > middle:
        return binary_search(middle, right)
    elif count < middle:
        return binary_search(left, middle)
    else:
        return middle
print(binary_search(0,10**10))

Submission status: Accepted

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

n,a,b=map(int,input().split())
x=a-b
h=[int(input()) for _ in range(n)]
ok=10**9+1
ng=0
while ok-ng>1:
    m=(ok+ng)//2
    k=0
    for i in range(n):
        k+=(max(0,h[i]-m*b)+x-1)//x
    if k<=m:
        ok=m
    else:
        ng=m
print(ok)

Submission status: Accepted

Solution code:
import heapq
from math import ceil

def check(ls,mid,a,b):
    count = 0
    for now in ls:
        now -= mid*b
        count += ceil(max(now,0)/(a-b))
    if count<=mid:
        return True
    else:
        return False

def main():
    n,a,b = map(int,input().split())
    h = [int(input()) for _ in range(n)]
    can_l,can_r = 0,10**9
    while 1:
        if can_r==can_l:
            print(can_r)
            exit()
        elif abs(can_r-can_l)==1:
            if check(h,max(can_r,can_l),a,b):
                print(max(can_l,can_r))
                exit()
            else:
                print(min(can_l,can_r))
                exit()
        mid = ceil((can_l+can_r)/2)
        if check(h,mid,a,b):
            can_r = mid
        else:
            can_l = mid
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
H=[int(input()) for _ in range(n)]
r=10**10
l=0
while r-l>1:
    k=(l+r)//2
    if sum( max(0,(h-k*b-1)//(a-b)+1) for h in H)>k:
        l=k
    else:
        r=k

print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, a, b = LI()
H = IR(n)
ok = 10 ** 9
ng = 0
while ok > ng + 1:
    mid = (ok + ng) // 2
    ret = 0
    for h in H:
        remain = h - b * mid
        if remain > 0:
            ret += remain // (a - b) + bool(remain % (a - b))
    if ret <= mid:
        ok = mid
    else:
        ng = mid


print(ok)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

from math import ceil

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

    def check(x):
        cnt=0
        for i in range(n):
            cnt+=ceil(max(0,H[i]-b*x)/a)
        return cnt<=x

    print(bisection(0,max(H),check,left=False))
resolve()

Submission status: Accepted

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


def f(n, H, A, B): #n回の爆発で魔物を全て倒せるか判定
    c = 0
    for i in range(len(H)):
        t = H[i]
        t -= B*n
        if t > 0:
            c += t//(A-B) + min(1, t%(A-B))
    if c > n:
        return False
    else:
        return True
    
    
def g(u, l, H, A, B): #魔物を倒すことができる爆発の最小回数を二分探索
    if u-l < 2:
        if f(l, H, A, B):
            return l
        else:
            return u
    m = (u+l)//2
    if f(m, H, A, B):
        return g(m, l, H, A, B)
    else:
        return g(u, m, H, A, B)
    
    
ans = g(10**9, 1, H, A, B)
print(ans)

Submission status: Accepted

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

import math
def enough(n):
    rest = [h - B * n * 1.0 for h in H]
    m = sum([ math.ceil(r/(A-B)) for r in rest if r > 0])
    return m <= n

l, r = 0, 10**9

while r - l > 1:
    mid = (l + r) // 2
    if enough(mid):
        r = mid

    else:
        l = mid

    # print(l, r, mid)

print(r)

Submission status: Accepted

Solution code:

def updiv(a,b):

    if a % b == 0:
        return a // b
    else:
        return a // b + 1

def able(n):

    nt = 0
    for i in range(N):
        if h[i] - B*n <= 0:
            continue
        nt += updiv(h[i] - B*n , A-B)
        #print (h[i],B,h[i]-B*n,A-B,nt)

    if nt <= n:
        return True
    else:
        return False

N,A,B = map(int,input().split())

h = []
for i in range(N):
    H = int(input())
    h.append(H)

l = 0
r = max(h)
lf = able(l)
rf = able(r)

while r - l != 1:

    m = (l + r) // 2
    mf = able(m)

    if not mf:
        l = m
        lf = mf
    else:
        r = m
        rf = mf

print (r)

Submission status: Accepted

Solution code:
import math

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


def check(n):
    d = n * B
    t = 0
    for h in H:
        if h <= d:
            continue
        t += (h - d + (A - B - 1)) // (A - B)
    return t <= n


lo, hi = 0, 10 ** 9

while lo < hi:
    mi = (lo + hi) // 2
    if check(mi):
        hi = mi
    else:
        lo = mi + 1

print(hi)

Submission status: Accepted

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

def hantei(p):
    global a,b
    tp = p
    fa = a - b
    for sh in h:
        sh -= b * p
        if sh > 0:
            tp -= (sh+fa-1) // fa
            if tp < 0:
                return False
    return True


def nibun(l,r):
    if r == l:
        return l
    f = (l+r)//2
    if hantei(f):
        return nibun(l,f)
    else:
        return nibun(f+1,r)

print(nibun(1,10**9))

Submission status: Accepted

Solution code:
def examD():
    N, A, B = LI()
    h = [I() for _ in range(N)]
    upper = max(h); lower = 1; cur = (upper+lower)//2
    while (True):
        curne = 0
        for i in h:
            if i-cur*B>0:
                curne  += (i-cur*B-1)//(A-B) +1
        if upper - lower >= 2:
            if curne > cur:
                #条件満たさない
                lower = cur
                cur = (cur + upper) // 2
            else:
                upper = cur
                cur = (cur + lower) // 2
        else:
            if curne > cur:
                #条件満たさない
                cur = upper
                curne = 0
                for i in h:
                    if i - cur * B > 0:
                        curne += (i - cur * B - 1) // (A - B) + 1
                if curne > cur:
                    break
            else:
                cur = lower
                curne = 0
                for i in h:
                    if i - cur * B > 0:
                        curne += (i - cur * B - 1) // (A - B) + 1
                if curne < cur:
                    ans = lower
                    break
            ans = upper
            break
    print(ans)



import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, A, B = map(int, input().split())
h = []
for _ in range(N):
  h.append(int(input()))
h.sort()
def explosive(x):
  c = 0
  for i in range(N):
    if h[i] > x * B:
      c += -(-(h[i] - x * B) // (A - B))
  if c <= x: return True
  else: return False
ng = 0
ok = 10 ** 9
m = 0
while ok - ng > 1:
  m = (ng + ok) // 2
  #print(m, explosive(m))
  if explosive(m):
    ok = m
  else:
    ng = m
print(ok)

Submission status: Accepted

Solution code:
import math

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


def ok(n):
    d = n * B
    t = 0
    for h in H:
        if h <= d:
            continue
        t += math.ceil((h - d) / (A - B))
        # t += (h - d) // (A - B)
    return t <= n


lo, hi = 0, 10 ** 9

while lo < hi:
    mi = (lo + hi) // 2
    if ok(mi):
        hi = mi
    else:
        lo = mi + 1

print(hi)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
c=a-b
h=[int(input()) for i in range(n)]
low=1
high=10**9+1
while high-low>0:
    k=(high+low)//2
    count=0
    for u in h:
        u-=b*k
        if u>0:
            if u%c==0:
                count+=u//c
            else:
                count+=u//c+1
    if high-low==1:
        if count<=k:
            print(k)
            break
        else:
            print(k+1)
            break
    else:
        if count<=k:
            high=k
        else:
            low=k

Submission status: Accepted

Solution code:
def turn_check(inlist,p,q,x):
    s = q*x
    t = p-q
    return sum([ (max(i-s,0)+t-1)//t for i in inlist ]) <= x

n, a, b = [ int(v) for v in input().split() ]
h_list = [ int(input()) for i in range(n) ]
ok, ng = 10**9, 0
while ok-ng > 1:
    mid = (ok+ng)//2
    if turn_check(h_list,a,b,mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
h=[]
for i in range(n):
    q=int(input())
    h.append(q)
left=0
right=max(h)+1
def en(t):
    cnt=0
    for i in range(n):
        if h[i]-b*t>0 and (h[i]-b*t)%(a-b)!=0:
            cnt+=((h[i]-b*t)//((a-b))+1)
        if h[i]-b*t>0 and (h[i]-b*t)%(a-b)==0:
            cnt+=((h[i]-b*t)//(a-b))
    if cnt<=t:
        return  True
    return  False
while left+1<right:
    tmp=(left+right)//2
    if en(tmp):
        right=tmp
    else:
        left=tmp
print(right)