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
n, a, b = map(int, input().split())
h_list = [int(input()) for _ in range(n)]

lb = 0
ub = 10**9 # これだけ唱えれば確実に全滅する

def is_ok(m):
    # m回の攻撃でモンスターが全滅するか
    tmp_ans = 0
    for h in h_list:
        tmp_h = max(h-m*b, 0) # モンスターの残り体力
        tmp_ans += math.ceil(tmp_h/(a-b)) # 爆発の中心になる回数
    if tmp_ans <= m:
        return True
    else:
        return False


ng = lb
ok = ub + 1
while ok - ng > 1:
    m = (ok + ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m

print(ok)

Submission status: Accepted

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

def is_ok(x):
    cnt = 0
    for i in range(n):
        h  = H[i]
        if h <= x*b:
            continue
        else:
            h -= x*b
            cnt += (h+(a-b-1))//(a-b)
    if cnt <= x:
        return True
    else:
        return False

l = 0
r = 19**18
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        r = c
    else:
        l = c
print(r)

Submission status: Accepted

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

l = 0
r = -(-maxh//b)
def ht(mid):
    cnt = 0
    for h in H:
        rem = h - b*mid
        if rem > 0:
            cnt += -(-rem//dab)
    return cnt <= mid

while (r-l) > 1:
    mid = (l + r) // 2
    if ht(mid):
        r = mid
    else:
        l = mid
print(r)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, A, B = getNM()
H = getArray(N)

def judge(time, main, sub, hp):
    diff = main - sub
    cnt = 0
    for i in range(len(hp)):
        left = hp[i] - time * sub
        if left > 0:
            cnt += (left + diff - 1) // diff

    return cnt

ok = 10 ** 12 + 1
ng = -1

while ok - ng > 1:
    mid = (ok + ng) // 2
    opt = judge(mid, A, B, H)

    # mid:仮のの回数
    # opt:midを定めた時必要な爆発の回数
    # 仮の回数が必要な回数より多ければokを緩和
    if mid >= opt:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
def check(T):
    res = 0
    for h in H:
        tmp = (h - B * T + A - B - 1) // (A - B)
        if tmp <= 0:
            break
        res += tmp
    return True if res <= T else False

N, A, B = map(int, input().split())
H = [int(input()) for _ in range(N)]
H.sort(reverse=True)
res = 0
left = 0
right = 10 ** 9
while right != left:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid + 1
print(left)

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    n, a, b, *k = map(int, open(0).read().split())
    k.sort()

    l = k[-1] // a
    r = k[-1] // b + 1
    m = (l + r) // 2
    while l + 1 < r:
        c = sum(ceil((i - m * b) / (a - b)) if i - m * b > 0 else 0 for i in k)
        (l, r) = (l, m) if c <= m else (m, r)
        m = (l + r) // 2

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    n, a, b, *k = map(int, open(0).read().split())
    k.sort()

    l = k[-1] // a
    r = k[-1] // b + 1
    m = (l + r) // 2
    while l + 1 < r:
        c = sum(ceil((i - m * b) / (a - b)) if i - m * b > 0 else 0 for i in k)
        if c <= m:
            r = m
        else:
            l = m

        m = (l + r) // 2

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    n, a, b, *k = map(int, open(0).read().split())
    k.sort()

    l = k[-1] // a - 1
    r = k[-1] // b + 1
    m = (l + r) // 2
    while l + 1 < r:
        c = sum(ceil((i - m * b) / (a - b)) if i - m * b > 0 else 0 for i in k)
        if c <= m:
            r = m
        else:
            l = m

        m = (l + r) // 2

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    n, a, b, *k = map(int, open(0).read().split())
    k.sort()

    l = 0
    r = k[-1]
    m = (l + r) // 2
    while l + 1 < r:
        c = sum(ceil((i - m * b) / (a - b)) if i - m * b > 0 else 0 for i in k)
        if c <= m:
            r = m
        else:
            l = m
        m = (l + r) // 2

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    from copy import deepcopy
    n, a, b, *k = map(int, open(0).read().split())
    k.sort()

    def check(x):
        q = deepcopy(k)
        cnt = 0
        while q:
            p = q.pop() - x * b
            if p <= 0:
                break
            cnt += ceil(p / (a - b))

        return cnt <= x

    l = 0
    r = k[-1]
    m = (l + r) // 2
    while l + 1 < r:
        if check(m):
            r = m
        else:
            l = m
        m = (l + r) // 2

    print(m+1)


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 = max(h)

def f(x):
    res = 0
    for i in range(n): res += max(0,(h[i]-b*x+a-b-1))//(a-b)
    return res <= x

while l+1 < r:
    m = (l+r)//2
    if f(m): r = m
    else: l = m
print(r)

Submission status: Accepted

Solution code:
from math import ceil
n,a,b = map(int,input().split())
h = [int(input()) for _ in range(n)]
l = 0
r = max(h)

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

while l+1 < r:
    m = (l+r)//2
    if f(m): r = m
    else: l = m
print(r)

Submission status: Accepted

Solution code:
def binsearch(good, bad, fn):
    while abs(good - bad) > 1:
        m = (good + bad) // 2
        if fn(m):
            good = m
        else:
            bad = m
    return good

def main():
    N, A, B = map(int, input().split())
    H = [int(input()) for _ in range(N)]
    c = A - B
    def helper(x):
        r = 0
        for h in H:
            r += max((h - B * x + c - 1) // c, 0)
        return r <= x

    return binsearch(10**9, 0, helper)

print(main())

Submission status: Accepted

Solution code:
import math
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

def main():
    N, A, B = map(int, input().split())
    l = []
    C = A - B
    for _ in range(N):
        h = int(input())
        l.append(h)
    def func(i):
        if max(l) <= B*i:
            return False
        r = 0
        for j in l:
            r += max(math.ceil((j - B*i) / C), 0)
        if r <= i:
            return False
        return True
    return 1 + binsearch(0, 1000000000, func)

print(main())

Submission status: Accepted

Solution code:
import sys
S=sys.stdin.readlines()
N,A,B=map(int,S[0].split())
H=[int(S[i+1]) for i in range(N)]
L,R=0,10**9
M=0
Z=0
A-=B
while R>L:
  M=(L+R)//2
  Z=0
  for i in range(N):
    Z+=max((H[i]-B*M+A-1)//A,0)
  if Z>M:
    L=max(L+1,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)]
def bisearch(k):# k回で倒せるかどうか
  ret=0
  for hi in h:
    ret+=max(0,(hi-b*k+a-b-1)//(a-b))
  return ret<=k
l,r=0,pow(10,9)
while r-l>1:
  x=(l+r+1)//2
  if bisearch(x):
    r=x
  else:
    l=x

print(r)

Submission status: Accepted

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

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

# AをA - Bと読み替え、一回の攻撃で全体にBダメージと1体にAダメージと考える
# X回で達成できるかの二分探索

A -= B

ng = 0
ok = 10 ** 9
def isOk(x):
  # 各H_iを倒すのに必要な攻撃Aの回数をカウントする
  cnt = 0
  for i in range(len(H)):
    h = H[i] - x * B
    if h > 0:
      cnt += (h + A - 1) // A
  return cnt <= x
  
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())
c = a-b
h = sorted([int(input()) for _i in range(n)], reverse=True)
left, right = 0, 10**9
while left < right:
    middle = (left+right)//2
    counter = 0
    checker = middle*b
    i = 0
    while checker < h[i]:
        counter -= (-h[i]+checker)//c
        i += 1
        if i >= n:
            break
    if counter <= middle:
        right = middle
    else:
        left = middle + 1
print(right)

Submission status: Accepted

Solution code:
import numpy as np

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

hi = 10**10
low = -1

def calc(x):
    y = h-x*b
    y[y<0] = 0
    f = np.ceil(y/(a-b)).sum()
    return f

while hi-low > 1:
    ave = (hi+low)//2
    if calc(ave) <= ave:
        hi = ave
    else:
        low = ave
    
print(hi)

Submission status: Accepted

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

def judge(t):
    base_damage=B*t
    add_attack=0
    for hi in H:
        if hi <= base_damage:
            continue
        res=hi-base_damage
        q,r=divmod(res,A-B)
        add_attack+=q
        if r:
            add_attack+=1
    return add_attack<=t

MAX=max(H)
max_attack=MAX//B+1
min_attack=0
while True:
    mid=(min_attack+max_attack)//2
    if mid==min_attack:
        break
    else:
        if judge(mid):
            max_attack=mid
        else:
            min_attack=mid
print(max_attack)

Submission status: Accepted

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


def isOk(k):
    return k >= 0


ok, ng = max(h)//B+1, 0
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    c = mid
    for i in range(N):
        t = h[i]-mid*B
        if t > 0:
            c -= (t+A-B-1)//(A-B)
            if c < 0:
                break
    if isOk(c):
        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)]
h.sort()


def isOk(k):
    return k >= 0


ok, ng = max(h)//B+1, -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    c = mid
    for i in range(N):
        t = h[i]-mid*B
        if t > 0:
            c -= (t+A-B-1)//(A-B)
            if c < 0:
                break
    if isOk(c):
        ok = mid
    else:
        ng = mid

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)]
C = A - B

hi = 10**9 + 1
lo = -1

while hi - lo > 1:
    mid = (hi + lo) // 2
    rem = 0
    for i in range(N):
        rem += max(0, (H[i] - B * mid + C - 1) // C)
    if rem <= mid:
        hi = mid
    else:
        lo = mid

print(hi)

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
H = []
for _ in range(N):
    H.append(int(input()))
H = sorted(H)
def check(x):
    cnt = 0
    for h in H:
        if h > x * B:
            tmp = (h - x*B) // (A-B)
            #切り上げ
            if tmp * (A-B) != h - x*B: tmp += 1
            cnt += tmp
    if cnt <= x:
        return True
    else:
        return False
# (l,r]
def bisect(l,r):
    if r - l == 1: return r
    mid = (l+r) // 2
    if check(mid):
        return bisect(l,mid)
    else:
        return bisect(mid,r)
    
print(bisect(0,10**12))

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
H = []
for _ in range(N):
    H.append(int(input()))
H = sorted(H)
def check(x):
    cnt = 0
    for h in H:
        if h > x * B:
            tmp = (h - x*B) // (A-B)
            #切り上げ
            if tmp * (A-B) != h - x*B: tmp += 1
            cnt += tmp
    if cnt <= x:
        return True
    else:
        return False
# (l,r]
def bisect(l,r):
    if r - l == 1: return r
    mid = (l+r) // 2
    if check(mid):
        return bisect(l,mid)
    else:
        return bisect(mid,r)
    
print(bisect(0,10**31))

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
H = []
for _ in range(N):
    H.append(int(input()))
H = sorted(H)
def check(x):
    cnt = 0
    for h in H:
        if h > x * B:
            tmp = (h - x*B) // (A-B)
            #切り上げ
            if tmp * (A-B) != h - x*B: tmp += 1
            cnt += tmp
    if cnt <= x:
        return True
    else:
        return False
# (l,r]
def bisect(l,r):
    if r - l == 1: return r
    mid = (l+r) // 2
    if check(mid):
        return bisect(l,mid)
    else:
        return bisect(mid,r)
    
print(bisect(0,10**28))

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
H = []
for _ in range(N):
    H.append(int(input()))
H = sorted(H)
def check(x):
    cnt = 0
    for h in H:
        if h > x * B:
            tmp = (h - x*B) // (A-B)
            #切り上げ
            if tmp * (A-B) != h - x*B: tmp += 1
            cnt += tmp
    if cnt <= x:
        return True
    else:
        return False
# (l,r]
def bisect(l,r):
    if r - l == 1: return r
    mid = (l+r) // 2
    if check(mid):
        return bisect(l,mid)
    else:
        return bisect(mid,r)
    
print(bisect(0,10**20))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,a,b = map(int, input().split())
hs = [None]*n
for i in range(n):
    hs[i] = int(input())
    
def sub(x):
    vs = [max(item - b*x, 0) for item in hs]
    return sum(v // (a-b) + bool(v % (a-b)) for v in vs) <= x

l = 0
r = 10**9

while l<r-1:
    m = (l+r)//2
    if sub(m):
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

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

def main():
    n,a,b = map(int,input().split())
    h = [int(input()) for _ in range(n)]
    ok = max(h)
    ng = 0
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        for i in range(n):
            cnt += max(0, math.ceil((h[i]-mid*b)/(a-b)))
        if cnt <= mid:
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def submit():
    n, a, b = (int(e) for e in input().split())
    h = [int(input()) for _ in range(n)]

    # t回で倒せるか否かを判定する処理を実施し、
    # tについて2分探索する

    def judge(t):
        base_damage = b * t
        add_attack = 0
        for hi in h:
            if hi <= base_damage:
                continue
            res = hi - base_damage
            q, r = divmod(res, a - b)
            add_attack += q
            if r:
                add_attack += 1
        return add_attack <= t

    max_attack = 0
    for hi in h:
        max_attack += hi // a + 1
    min_attack = 0
    while True:
        mid = (min_attack + max_attack) // 2
        if mid == min_attack:
            break
        else:
            if judge(mid):
                max_attack = mid
            else:
                min_attack = mid

    print(max_attack)

             
if __name__ == "__main__":
    submit()

Submission status: Accepted

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

def check(x):
  time = 0
  _H = [h-B*x for h in H]
  for _h in _H:
    if _h > 0:
      time += -(-_h//diff)
  return time <= x

left = 0 # False
right = 10**10 # True
while left + 1 < right:
  mid = (left + right) // 2
  if check(mid):
    right = mid
  else:
    left = mid

print(right)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

N, A, B = map(int, sys.stdin.readline().strip().split())

H = []
for _ in range(N):
    H.append(int(sys.stdin.readline().strip()))
H.sort()

# 二分探索でmid回の攻撃で魔物を消し去れるか
left = 1
right = 10**9

# うまくいかないのでansを保持しておく
ans = right
while left < right:
    mid = (left + right) // 2
    # print(mid)
    n = mid
    for h_i in H:
        if h_i <= B * mid:
            continue

        # Bの攻撃のみで消し去れない場合はAの攻撃を消費する
        h_i -= B * mid
        n -= (h_i - 1) // (A-B) + 1

    if n >= 0:
        ans = min(ans, mid)
    if n == 0:
        break
    elif n > 0:
        right = mid
    else:
        left = mid + 1

print(ans)

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

#二分探索用のコード

#(1)l,rは両端点でl<=r
l,r=0,10**9
#(2)l=rもしくはl=r-1のときにbreak
while l+1<r:
    #(3)その閉区間の中点(の小数部分を切り捨てたもの)
    #オーバーフローを考慮すると以下の書き方になる
    k=l+(r-l)//2
    #ここでは境目以上のxで真になるので、
    #x=kで真の場合は大きい方の端点をkにし、x=kで偽の場合は小さい方の端点をkにする
    if explode(k):
        r=k
    else:
        l=k

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 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

#二分探索用のコード

#(1)l,rは両端点でl<=r
l,r=1,10**9
#(2)l=rもしくはl=r-1のときにbreak
while l+1<r:
    #(3)その閉区間の中点(の小数部分を切り捨てたもの)
    #オーバーフローを考慮すると以下の書き方になる
    k=l+(r-l)//2
    #ここでは境目以上のxで真になるので、
    #x=kで真の場合は大きい方の端点をkにし、x=kで偽の場合は小さい方の端点をkにする
    if explode(k):
        r=k
    else:
        l=k

print(l if explode(l) else r)

Submission status: Accepted

Solution code:
import math


def check(k, A, B, H):
    return sum([max([0, math.ceil((h - B * k) / (A - B))]) for h in H]) <= k


def main():
    N, A, B = list(map(int, input().split(' ')))
    H = [int(input()) for _ in range(N)]
    ng, ok = 0, 10**9
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if check(mid, A, B, H):
            ok = mid
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
h=[int(input())for _ in range(n)]
h.sort(reverse=True)
l=-1
r=(max(h)-1)//b+1
while r-l>1:
	mid=(l+r)//2
	cnt=0
	for i in range(n):
		if h[i]-b*mid<=0:
			break
		else:
			cnt+=(h[i]-b*mid-1)//(a-b)+1
	if cnt>mid:
		l=mid
	else:
		r=mid
print(r)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
h=[int(input())for _ in range(n)]
h.sort(reverse=True)
l=-1
r=10**9
while r-l>1:
	mid=(l+r)//2
	cnt=0
	for i in range(n):
		if h[i]-b*mid<=0:
			break
		else:
			cnt+=(h[i]-b*mid-1)//(a-b)+1
	if cnt>mid:
		l=mid
	else:
		r=mid
print(r)

Submission status: Accepted

Solution code:
N, A, B = map(int,input().split())
h = []
for _ in range(N):
    h.append(int(input()))
 
def solve(n):
    cnt = 0
    for i in h:
        i -= B * n
        cnt += max((i - 1) // (A - B) + 1, 0)
    return cnt <= n
 
left = 0
right = 10 ** 9

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid
 
print(right)

Submission status: Accepted

Solution code:
from math import ceil

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


def defeatable(k):
    hb = [max([h - k * b, 0]) for h in hs]
    n_attack = sum([ceil(h / (a - b)) for h in hb])
    return n_attack <= k


l, r = 0, ceil(max(hs) / b)

while r - l > 1:
    m = (l + r) // 2

    if defeatable(m):
        r = m
    else:
        l = m

print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    # class MaxHeap:
    #     def __init__(self, seq):
    #         tmp = list(map(lambda x: -x, seq))
    #         heapify(tmp)
    #         self.h = tmp
    #     def push(self, num):
    #         heappush(self.h, - num)
    #     def pop(self):
    #         return -heappop(self.h)

    # n, a, b = mi()
    # hp = MaxHeap([ii() for _ in range(n)])
    # cnt = 0
    # while True:
    #     max_hp = hp.pop()
    #     if max_hp <= cnt * b:
    #         break
    #     else:
    #         hp.push(max_hp - (a - b))
    #         cnt += 1
    # print(cnt)

    def ceil_div_alternative(x, y):
        """
        Args:
            x, y (int)
        Returns:
            int
        
        ceil(x / y) を正確に返す (y を何整数倍すると x 以上になるか？の値)

        >>> ceil_div_alternative(4, 2)
        2
        >>> ceil_div_alternative(4, 3)
        2

        > ceil() 、 floor() 、および modf() 関数については、非常に大きな浮動小数点数が 全て 整数そのものになるということに注意してください。
        > 通常、Python の浮動小数点型は 53 ビット以上の精度をもたない (プラットフォームにおける C double 型と同じ) ので、
        > 結果的に abs(x) >= 2**52 であるような浮動小数点型 x は小数部分を持たなくなるのです。
        > 10 ** 15 + 0.2 == 10 ** 15
        > False
        > 10 ** 16 + 0.2 == 10 ** 16
        > True
        
        x / y が大きな浮動小数点数となる場合は ceil ではなく、この関数を使うようにする。
        """
        assert (isinstance(x, int) and isinstance(y, int))
        assert (x >= 0 and y > 0)
        return (x + y - 1) // y


    def can_defeat_predicate(hp_list, operation_times, a, b):
        n = len(hp_list)
        start = bisect_right(hp_list, b * operation_times)
        if start == n:
            return True
        else:
            res = [hp_list[i] - b * operation_times for i in range(start, n)]
            cnt = 0
            for elm in res:
                cnt += ceil_div_alternative(elm, a - b)
            return cnt <= operation_times


    def binary_search(hp_list, a, b):
        left = 0    # 絶対に倒せない操作回数
        right = 10**9+1    # 絶対に倒せる操作回数
        while right - left > 1:
            mid = (right + left) // 2
            if can_defeat_predicate(hp_list, mid, a, b):
                right = mid
            else:
                left = mid
        return right



    n, a, b = mi()
    hp = sorted([ii() for _ in range(n)])
    print(binary_search(hp, a, b))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,a,b = inpl()
h = [inp() for _ in range(n)]
ok = 10**12
ng = 0
c = a-b
def chk(x):
    cnt = 0
    for t in h:
        t -= b*x
        if t <= 0: continue
        cnt += (t+c-1)//c
    if cnt <= x:
        return True
    return False
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if chk(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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

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

left = 0
right = 10**10

def solve(x):
    remain = []
    for i in h:
        i -= b*x
        if i > 0:
            remain.append(i)
    cnt = 0
    for i in remain:
        cnt += i // (a - b) + int(i % (a - b) != 0)
    if cnt <= x:
        return True
    else:
        return False

while right - left > 1:
    mid = (right + left) // 2
    if solve(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
import numpy as np
N, A, B = map(int, input().split())
h = np.sort([int(input()) for i in range(N)])

def enough(A, B, h, T):
    h = np.ceil((h - B * T) / (A - B))
    count = sum(h[h > 0])
    
    return True if count <= T else False
right = 10 ** 9
left = 1
while right != left:
    mid = (left + right) // 2
    if enough(A, B, h, mid):
        right = mid
    else:
        left = mid + 1

print(left)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,a,b = map(int,input().split())
h = [int(input()) for i in range(n)]
t = a-b
r = (max(h)+b-1)//b
l = 0
while r-l > 1:
    m = (r+l)//2
    mi = m*b
    count = 0
    for i in h:
        if i > mi:
            count += (i-mi+t-1)//t
    if count <= m:
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
h = [int(input()) for i in range(n)]
t = a-b
r = (max(h)+b-1)//b
l = 0
while r-l > 1:
    m = (r+l)//2
    mi = m*b
    count = 0
    for i in h:
        if i > mi:
            count += (i-mi+t-1)//t
    if count <= m:
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort()
t = a-b
r = 10**9+5
l = 0

while r-l > 1:
    m = (r+l)//2
    mi = m*b
    count = 0
    for i in h:
        if i > mi:
            count += (i-mi+t-1)//t
    if count <= m:
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
n,a,b = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort()
t = a-b
r = 10**9+5
l = 0

while r-l > 1:
    m = (r+l)//2
    mi = m*b
    count = 0
    for i in h:
        if i > mi:
            count += (i-mi+t-1)//t
    if count <= m:
        r = m
    else:
        l = m
print(r)