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:
N,A,B = map(int, input().split())
hs = [int(input()) for _ in range(N)]

def f(x):
    """
    xが少ないとfalse
    xが大きいとtrue
    """
    As = [max(0,h-B*x) for h in hs]
    Bs = [-(-a//(A-B)) for a in As]
    
    return sum(Bs) <= x


def  binarySearch(l,r):
    while r - l > 1:
        mid = (l+r)//2
        if f(mid):
            r = mid
        else:
            l = mid
    return r


r = 10**9+1
print(binarySearch(0,r))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
import numpy as np

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

    a -= b
    def ok(x): #x回の爆発で倒せるか
        list = (H - b * x + a - 1)//a
        return sum(list[list>0]) <=  x
    
    l = -1
    r = 10 ** 10
    while r - l > 1:
        mid = (r + l)//2
        if ok(mid):
            r = mid
        else:
            l = mid  
    print(r)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
import numpy as np

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

    a -= b
    def ok(x): #x回の爆発で倒せるか
        list = (H - b * x + a - 1)//a
        return list[list>0].sum() <=  x
    
    l = -1
    r = 10 ** 10
    while r - l > 1:
        mid = (r + l)//2
        if ok(mid):
            r = mid
        else:
            l = mid  
    print(r)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B=map(int,input().split())
h=[int(input()) for i in range(N)]
h.sort(reverse=1)
l,r=0,10**9
k=A-B
while l+2<r:
    m=(r-l)//2+l
    t=m*B
    c=0
    for i in h:
        if i>t:
            c+=-((-i+t)//k)
        else:
            break
    if c>m:
        l=m
    else:
        r=m+1
print(r-1)

Submission status: Accepted

Solution code:
#A
if False:
    N=int(input())
    E=[int(i) for i in input().split()]
    E.sort()
    s=sum(E)
    if E[-1]<s-E[-1]:
        print('Yes')
    else:
        print('No')
#B
if False:
    N=int(input())
    fac=[]
    for i in range(1,10**6+1000):
        if N%i==0:
            fac.append((i,N//i))
    ans=10**19
    for l,r in fac:
        ans=min(l-1+r-1,ans)
    print(ans)
  
#C
if False:
    N=int(input())
    S=[input() for _ in range(N)]
    march=list('MARCH')
    nam=[[] for _ in range(len(march))]
    for s in S:
        if s[0] in march:
            nam[march.index(s[0])].append(s)
    ans=0
    for i in range(5):
        for j in range(i+1,5):
            for k in range(j+1,5):
                ans+=len(nam[i])*len(nam[j])*len(nam[k])
    print(ans)

#D
if False:
    import sys

    if sys.getrecursionlimit()<10**7:
        sys.setrecursionlimit(10**7)

    N=int(input())
    ver=[[] for _ in range(N)]
    for _ in range(N-1):
        u,v,W=map(int,input().split())
        ver[u-1].append((v-1,W))
        ver[v-1].append((u-1,W))
    his=[-1 for _ in range(N)]

    def dfs(i,col):
        his[i]=col
        for j,w in ver[i]:
            if his[j]==-1:
                if w%2==0:
                    dfs(j,col)
                else:
                    dfs(j,(col+1)%2)

    dfs(0,0)            
    for i in range(N):
        print(his[i])

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

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

def eno(T):
    nee=0
    td=B*T
    dd=A-B
    for h in H:
        if h-td>0:
            nee+=ceil(h-td,dd)
    return nee<=T

l,r=0,10**9+7
while l+1<r:
    mid=(l+r)//2
    if eno(mid):
        r=mid
    else:
        l=mid
print(r)

Submission status: Accepted

Solution code:

def main():
    import math
    N, A, B = map(int, input().split())
    h = [int(input()) for i in range(N)]
    d = A - B

    l = 1
    r = max(h)
    while(l+1 < r):
        m = (l+r)//2
        t = m*B
        count = 0
        for x in h:
            if x > t:
                count += math.ceil((x-t)/d)
        if count <= m:
            r = m
        else:
            l = m

    print(r)


main()

Submission status: Accepted

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

    def is_ok(x):
        need = 0
        cur = [0]*N
        for i, h in enumerate(H):
            cur.append(max(0, h - B*x))
        for i, less in enumerate(cur):
            need += (less+(A-B)-1)//(A-B)
        if need <= x:
            return True
        else:
            return False

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

    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ok = 10**18
ng = 0

def isOk(n):
    cnt = 0
    for h in H:
        h -= B * n
        if h > 0:
            cnt += -(-h // (A - B))
    return cnt <= n

while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, a, b = MAP()
h = [INT() for _ in range(n)]
ad = a - b
l = 1
r = 10 ** 9
while r - l > 1:
    c = (r + l) // 2
    cnt = 0
    for i in range(n):
        cnt += (max(h[i] - b * c, 0) + ad - 1) // ad
    if c > cnt:
        r = c
    else:
        l = c
ans = inf
for i in range(l, r + 1):
    cnt = 0
    for j in range(n):
        cnt += (max(h[j] - b * i, 0) + ad - 1) // ad
    ans = min(ans, max(i, cnt))
print(ans)

Submission status: Accepted

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

def check(X):
    """ X回以下の爆発で全滅するか """
    ans = 0
    for h in H:
        cnt = ((h - B * X) + (A - B) - 1) // (A - B)
        ans += max(0, cnt)
    return ans <= X

def main():
    ng = 0
    ok = 10 ** 10
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    under = 0
    r = (max(H) + B - 1) // B
    c = A - B
    while r - under > 1:
        m = (r + under) // 2
        rem = 0
        for hi in H:
            hi -= B*m
            if hi <= 0: continue
            rem += (hi + c - 1) // c
        if rem <= m: r = m
        else: under = m
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, A, B = map(int, input().split())
    H = [int(input()) for _ in range(N)]
    low = 0; high = 10 ** 20
    while high - low > 1:
        mid = (low + high) // 2
        explosion = B * mid
        direct = 0
        for h in H:
            if h - explosion > 0:
                direct += (h - explosion) // (A - B)
                if (h - explosion) % (A - B) > 0: direct += 1
        if direct <= mid: high = mid
        else: low = mid
    print(high)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

l = 0
r = 10**10
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)

Submission status: Accepted

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

def is_ok(k):
    hp = []
    for h in H:
        if h - B*k > 0:
            hp.append(h - B*k)
    if len(hp)==0: return True
    x = 0
    for h in hp:
        x += 0--h//(A-B)
        if x > k: return False
    return True

ok = 10**14
ng = 0
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)]

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

Submission status: Accepted

Solution code:
N, A, B , *h = map(int, open(0).read().split())
C = A-B
l = -1
r = 10**12
while l+1<r:
  s = (l+r)//2
  cnt = sum((c-s*B+C-1)//C if c-s*B>0 else 0 for c in h)
  if cnt>s:
    l = s
  else:
    r = s
print(r)

Submission status: Accepted

Solution code:
N, A, B , *h = map(int, open(0).read().split())
C = A-B
l = -1
r = 10**20
while l+1<r:
  s = (l+r)//2
  M = [c-s*B for c in h]
  cnt = sum((c+C-1)//C if c>0 else 0 for c in M)
  if cnt>s:
    l = s
  else:
    r = s
print(r)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy

N,A,B=map(int,input().split())
H=[int(input()) for i in range(N)]
H.sort()
ng=0
ok=10**18
A-=B
while ok-ng>1:

    mid=(ok+ng)//2
    c=bisect_right(H,mid*B)

    _sum=0
    for i in range(c,N):
        Z=H[i]-mid*B
        _sum+=Z//A+bool(Z%A)
    #print(_sum)
    if mid>=_sum:
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Accepted

Solution code:
import numpy as np

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


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


l = 0
r = np.ceil(max(h) / b).astype(np.int64)
while r - l > 1:
    mid = (l + r) // 2
    if f(mid):
        r = mid
    else:
        l = mid

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


def f(x):
    cnt = 0
    for e in h:
        cnt += max(0, ceil((e - b * x) / (a - b)))

    if cnt > x:
        return False

    return True


l = 0
r = ceil(max(h) / b)
while r - l > 1:
    mid = (l + r) // 2
    if f(mid):
        r = mid
    else:
        l = mid

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


def f(x):
    cnt = 0
    for e in h:
        cnt += max(0, ceil((e - b * x) / (a - b)))

    if cnt > x:
        return False

    return True


l = 0
r = 10 ** 9 + 1
while r - l > 1:
    mid = (l + r) // 2
    if f(mid):
        r = mid
    else:
        l = mid

print(r)

Submission status: Accepted

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

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

ok=10**9+1
ng=0

while ok-ng>1:
    mid=(ok+ng)//2
    dmg=B*mid
    tgt=0
    for item in H:
        tgt+=-(-max(item-dmg,0)//(A-B))
    if tgt<=mid:
        ok=mid
    else:
        ng=mid

print(ok)

Submission status: Accepted

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

def hantei(now):
    ab=a-b
    nokori = sum(kiriage( max(0,hh-now*b) ,ab)//ab  for hh in h)
    return nokori<=now
def kiriage(x,c):
    if x%c==0:
        return x
    else:
        return (x//c+1) *c

ma = 10**9 +1
mi = 1

while mi<ma:
    now=(mi+ma)//2
    which = hantei(now)
#     print(which,mi,now,ma)
    if which:
        ma=now
        ans=now
    else:
        mi=now+1
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
def check(x,hp):
    hp=[hh-(b*x) for hh in hp]
    cnt=0
    for p in hp:
        if p<=0:continue
        cnt+=ceil(p/(a-b))
    return cnt<=x

n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]
lo=0
hi=10**9
while hi-lo>1:
    mid=(hi+lo)//2
    if check(mid,h):
        hi=mid
    else:
        lo=mid
ans=hi
# htとloどちらを出力すればよい？
# print(lo)
print(hi)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,A,B=MI()
    h=[0]*N
    for i in range(N):
        h[i]=I()
        
    def ch(X):
        #X回で達成できるか?
        temp=0
        for i in range(N):
            hp=h[i]-X*B
            if hp>0:
                temp+=(hp+A-B-1)//(A-B)
        if temp<=X:
            return True
        return False
    
    ng=0
    ok=10**9
    
    while abs(ok-ng)>1:
        x=(ok+ng)//2
        if ch(x):
            ok=x
        else:
            ng=x
    print(ok)
        

main()

Submission status: Accepted

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

def check(X):
  base = B * X
  counts = sum([max((h - base + dAB - 1)//dAB, 0) for h in Hn])
  return counts <= X
               
def min_binary_search(check, l=0, r=100000000000):
    while r - l > 1:
      mid = (l + r) // 2
      if check(mid):
        r = mid
      else:
        l = mid
    return r
print(min_binary_search(check))

Submission status: Accepted

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

    def is_ok(H, mid):
        H = [h - mid*B for h in H]
        need = 0
        for h in H:
            if h > 0:
                need += (h + (A - B) - 1)//(A - B)
        if need <= mid:
            return True
        else:
            return False

    def binary_search_meguru(H):
        ng = -1
        ok = 10**9 + 1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2  # 爆破回数
            if is_ok(H, mid):
                ok = mid
            else:
                ng = mid
        return ok

    print(binary_search_meguru(H))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil

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

# C回以下の爆発で倒せるか
def is_all_kill(C:int):
    cnt = 0
    for HP in h:
        # あるモンスターに中心ダメージを何回与えるか
        tmp = ceil((HP-B*C)/(A-B))
        # オーバーキルの場合
        if tmp <= 0:
            break
        cnt += tmp
    return cnt <= C

ok = 10 ** 18
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_all_kill(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)]

def ok(x):
    tot = 0
    for i in range(n):
        if b*x >= H[i]:
            continue
        else:
            r = H[i] - b*x
            if r%(a-b) == 0:
                tot += r//(a-b)
            else:
                tot += r//(a-b)+1
    if tot <= x:
        return True
    else:
        return False

l = 0
r = 10**10
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)

Submission status: Accepted

Solution code:
import numpy as np

N, A, B = map(int, input().split())
A -= B
H = np.array([int(input()) for _ in range(N)], dtype=np.int64)


def C(X):
    """
    x回爆発して、全部消滅させれるとTrue
    """
    HP = H - X * B
    HP = HP[HP > 0]
    cnt = (HP + A - 1) // A
    return cnt.sum() <= X


l = -1
r = 10 ** 18
while r - l > 1:
    m = (r + l) // 2
    if C(m):
        r = m
    else:
        l = m

ans = r
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, a, b = map(int, input().split())
    h = [int(input()) for _ in range(n)]
    low, high = 0, 1000000000000000000
    while low < high:
        mid = (low + high) // 2
        tmp = 0
        for _h in h:
            if _h > mid * b:
                tmp += (_h - mid * b + a - b - 1) // (a - b)
        if tmp > mid:
            low = mid + 1
        else:
            high = mid
    print(low)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

max_t = - (- max(H) // b)

def clear_or_not(a, b, t, H):
    count_t = 0
    for i in range(len(H)):
        need_t = -(-(H[i] - b*t) //(a-b))
        if need_t <= 0:
            need_t = 0
        count_t += need_t
    if count_t <= t:
        return True
    else:
        return False
\
def bisect(low=1, high=max_t):
    while high-low > 1:
        mid = low + (high-low)//2
        if clear_or_not(a,b,mid,H):
            high = mid
        else:
            low = mid
    return high
ans = bisect()

print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(x):
    k = b*x
    sm = 0
    for i in range(n):
        sm += max(0, (h[i]-k+c-1)//c)
    #ddprint(f"foo {x} sm {sm}")
    return (sm<=x)

n,a,b = inm()
h = []
for i in range(n):
    h.append(inn())
c = a-b
mn = 0
mx = (max(h)+b-1)//b
while mx>mn+1:
    mid = (mx+mn)//2
    if foo(mid):
        mx = mid
    else:
        mn = mid
print(mx)

Submission status: Accepted

Solution code:
import sys
import queue
import bisect

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main_b1():
	n, a, b = IN()
	al = [int(input()) for _ in range(n)]
	if len(al)==1:
		return (al[0] + a -1)//a
	
	al.sort()
	max_value = al[-1]
	min_value = al[0]
	dd_queue = queue.PriorityQueue()
	for v in al:
		dd_queue.put((-v, v))
		
	cc=0
	dmage_diff = a-b
	while True:
		_, max_hp=dd_queue.get()
		if max_hp-(b*cc) <= 0:
			return cc
			
		_, second_max_hp = dd_queue.get()
		nb = ((max_hp-second_max_hp)+dmage_diff-1)//dmage_diff
		
		if max_hp <= nb * a:
			return (max_hp + a - 1)//a
		
		cc += nb
		next_hp=max_hp-dmage_diff*nb
		dd_queue.put((-next_hp, next_hp))
		dd_queue.put((-second_max_hp, second_max_hp))

def is_ok(sorted_list, c, a, b):
	ii=bisect.bisect_right(sorted_list,b*c)
	count=c
	diff=a-b
	for v in sorted_list[ii:]:
		nokori = v - c*b
		count -= (nokori+diff-1)//diff
		if count < 0:
			return False
	return True

def main():
	n, a, b = IN()
	al = [int(input()) for _ in range(n)]
	al.sort()
	
	ok = (al[-1]+b-1)//b
	ng = 0
	while ok-ng > 1:
		mm=(ok+ng)//2
		if is_ok(al, mm, a, b):
			ok = mm
		else:
			ng = mm
	return ok
		
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, A, B = map(int, readline().split())
A = A - B
H = np.array([int(readline()) for _ in range(N)], dtype=np.int64)


def C(T):
    h = H-B*T
    h = h[h > 0]
    bomb = (h + A - 1) // A
    return bomb.sum() <= T


left = 0
right = 10 ** 18
while right - left > 1:
    mid = (right + left) // 2
    if C(mid):
        right = mid
    else:
        left = mid

ans = right
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


def C(T):
    """
    T回爆発させて、魔物全滅できるか
    """
    damage = B * T
    cnt = 0
    for h in H:
        h -= damage
        if h <= 0:
            continue
        cnt += (h + (A - B) - 1) // (A - B)
        if cnt > T:
            return False
    return cnt <= T


left = 0
right = 10 ** 18
while right - left > 1:
    mid = (right + left) // 2
    if C(mid):
        right = mid
    else:
        left = mid

ans = right
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


def C(T):
    """
    T回爆発させて、魔物全滅できるか
    """
    damage = B * T
    cnt = 0
    for h in H:
        h -= damage
        if h <= 0:
            continue
        cnt += (h + (A - B) - 1) // (A - B)
    return cnt <= T


left = 0
right = 10 ** 18
while right - left > 1:
    mid = (right + left) // 2
    if C(mid):
        right = mid
    else:
        left = mid

ans = right
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A, B = lr()
A -= B # 全員にBのダメージが加わるとする
H = np.array([ir() for _ in range(N)])

def check(x):
    hp = H - B*x
    hp = hp[hp>0]
    cnt = ((hp + A - 1) // A).sum()
    return cnt <= x

#二分探索
left = 0 #NG
right = 10 ** 9 #OK
while right > left + 1:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)
# 45

Submission status: Accepted

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

import math
def ok(x):
    t = 0
    for i in range(n):
        r = h[i] - b*x
        if r < 0:
            continue
        else:
            t += math.ceil(r/(a-b))
    if t <= x:
        return True
    else:
        return False

l = 0
r = 10**14+1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)

Submission status: Accepted

Solution code:
from math import ceil
n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]
def enough(x):
  cnt=0
  for i in range(n):
    if h[i]-x*b<=0:
      continue
    cnt+=ceil((h[i]-x*b)/(a-b))
  if cnt<=x:
    return True
  else:
    return False
l=0
r=10**9
while r-l>0:
  mid=(r+l)//2
  if enough(mid):
    r=mid
  else:
    l=mid+1
print(r)

Submission status: Accepted

Solution code:
# ABC063 D - Widespread
def check(x,hp):
    hp=[hh-(b*x) for hh in hp]
    explosion=0
    for hhh in hp:
        if hhh<=0:continue
        if hhh%(a-b)==0:
            explosion+=hhh//(a-b)
        else:
            explosion+=hhh//(a-b)+1
    return explosion<=x

n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]
lo=0
hi=10**9
while hi-lo>1:
    mid=(hi+lo)//2
    if check(mid,h):
        hi=mid
    else:
        lo=mid
print(lo+1)

Submission status: Accepted

Solution code:
import math
N, A, B = map(int, input().split())
H = [int(input()) for i in range(N)]
l = 0
r = math.ceil(max(H))
ans = 0
d = A-B
while(1):
    if l+1 == r:
        ans = r
        break
    else:
        m = (l+r) // 2
        count = 0
        for i in range(N):
            if (H[i] - m*B) > 0:
                count += math.ceil((H[i]-m*B) / d)
        if count <= m:
            r = m
        else:
            l = m
print(ans)

Submission status: Accepted

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

right = max(monsters) // b + 1
left = 0

while left+1 < right:
    bomb_count = (left+right) // 2
    base_damage = bomb_count * b

    center_count = 0
    for hp in monsters:
        if hp <= base_damage:
            continue

        remaining_hp = hp - base_damage
        need_center = (remaining_hp + a-b-1) // (a-b)
        center_count += need_center

    if center_count <= bomb_count:
        right = bomb_count
    else:
        left = bomb_count

print(right)

Submission status: Accepted

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

    def is_ok(x):
        y = 0  # 中心爆破必要回数
        for i, h in enumerate(H):
            if h - x*B <= 0:
                continue
            le = 0
            ri = 10**9 + 1
            while ri - le > 1:
                mid = le + ((ri - le) // 2)
                if h - B*(max(x - mid, 0)) - A*mid <= 0:
                    ri = mid
                else:
                    le = mid
            y += ri
        if y <= x:  # 魔物を消し去るのが可能
            return True
        else:
            return False

    def binary_search_meguru():
        left = -1
        right = 10**9 + 1
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right

    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def f(n):
    cnt = 0
    flag = True
    for h in H:
        x = (h-B*n)//(A-B) + min((h-B*n)%(A-B), 1)
        cnt += max(0, x)
    if cnt <= n:
        return True
    else:
        return False
        
l = 0
r = 10**9
while r-l > 1:
    m = (r+l)//2
    if f(m):
        r = m
    else:
        l = m
        
if f(l):
    print(l)
else:
    print(r)

Submission status: Accepted

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

ok=10**9
ng=0

while abs(ok-ng)>1:
 mid=(ok+ng)//2

 l=[i-(mid*b) for i in h]
 cnt=0
 for j in l:
  if j<=0:
   continue
  cnt+=(j+a-b-1)//(a-b)

 if cnt<=mid:
  ok=mid
 else:
  ng=mid

print(ok)

Submission status: Accepted

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

h_sum=sum(h)

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

 l=[max(i-(mid*b),0) for i in h]
 cnt=0
 for j in l:

#  if j<=0:
#   continue

  if j%(a-b)==0:
   cnt+=j//(a-b)
  else:
   cnt+=j//(a-b)+1

 if cnt<=mid:
  ok=mid
 else:
  ng=mid

print(ok)

Submission status: Accepted

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

h_sum=sum(h)

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

 l=[i-(mid*b) for i in h]
 cnt=0
 for j in l:

  if j<=0:
   continue

  if j%(a-b)==0:
   cnt+=j//(a-b)
  else:
   cnt+=j//(a-b)+1

 if cnt<=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):
  h += [int(input())]

Th = 2*max(h)//B
Tl = 0
while Tl+1<Th:
  t = (Th+Tl)//2
  d = []
  for i in range(N):
    c = h[i]
    d += [c-B*t]
  for i in range(N):
    c = d[i]
    if c<=0:
      continue
    t -= c//(A-B) if c%(A-B)==0 else c//(A-B)+1
    if t<0:
      Tl = (Th+Tl)//2
      break
  else:
    Th = (Th+Tl)//2
print(Th)

Submission status: Accepted

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

Th = 2*max(h)//B
Tl = 0
while Tl+1<Th:
  t = (Th+Tl)//2
  d = []
  for i in range(N):
    c = h[i]
    d += [c-B*t]
  for i in range(N):
    c = d[i]
    if c<=0:
      continue
    t -= ceil(c/(A-B))
    if t<0:
      Tl = (Th+Tl)//2
      break
  else:
    Th = (Th+Tl)//2
print(Th)

Submission status: Accepted

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

Th = 2*max(h)//B
Tl = 0
while Tl+1<Th:
  t = (Th+Tl)//2
  d = []
  for i in range(N):
    c = h[i]
    d += [c-B*t]
  for i in range(N):
    c = d[i]
    if c<=0:
      continue
    t -= ceil(c/(A-B))
    if t<0:
      Tl = (Th+Tl)//2
      break
  else:
    Th = (Th+Tl)//2
print(Th)