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())
H = [0] * N
for i in range(N):
    H[i] = int(input())

sorted_H = sorted(H, reverse=True)

def is_enough(num):
    cnt = 0
    for x in range(N):
        if sorted_H[x] - num * B > 0:
            cnt += (sorted_H[x] - num * B) // (A - B)
            if (sorted_H[x] - num * B) % (A - B) != 0:
                cnt += 1
        else:
            break
    return cnt <= num

limit = (sorted_H[0] // B) + 1

i = 0
j = limit
while True:
    k = (j + i) // 2
    if is_enough(k):
        if i + 1 == k:
            print(k)
            break
        j = k
    else:
        if k + 1 == j:
            print(k + 1)
            break
        i = k

Submission status: Accepted

Solution code:
import sys
import math
def input():
    return sys.stdin.readline()[:-1]

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

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

low=0
high=max(h)
while high-low>1:
    mid=(low+high)//2
    if check(mid):
        high=mid
    else:
        low=mid
    # print(low)
    # print(high)
print(high)

Submission status: Accepted

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

ans=[0]*2

d=[]
for i in range(n):
    h=int(input())
    d.append(h)
d.sort(reverse=True)
ans[1]=max(d)
while ans[1]-ans[0]!=1:
    x=z=(ans[1]+ans[0])//2
    y=x*b
    for i in range(n):
        p=d[i]-y
        if p<=0:
            break
        x-=(p+t-1)//t
        if x<0:
            break
    if x<0:
        ans[0]=z
    else:
        ans[1]=z
print(ans[1])

Submission status: Accepted

Solution code:
from bisect import bisect_left
try:
    from collections.abc import Sequence
except:
    from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        if isinstance(n, int):
            self.r = range(n)
        elif isinstance(n, range):
            self.r = n
        else:
            raise TypeError

    def __len__(self):
        return len(self.r)

    def __getitem__(self, i):
        r = self.r[i]
        if isinstance(r, int):
            return self.f(r)
        else:
            return self.__class__(self.f, r)


N, A, B = map(int, input().split())
D = A - B
H = [int(input()) for _ in range(N)]
H.sort()
l = (H[0] - 1) // A + 1
r = (H[-1] - 1) // B + 1


def isenough(n):
    b = B * n
    for h in H:
        n -= max(0, (h - b - 1) // D + 1)
        if n < 0:
            return False
    return True


a = LazySequence(isenough, r + 1)
ans = bisect_left(a, True, l, r)
print(ans)

Submission status: Accepted

Solution code:
def calc(n):
    damage = (b * n)
    d = [max(dd - damage, 0) for dd in h]
    a_num = 0
    for i in range(len(d)):
        a_num += max(0, 1 + (d[i]-1) // (a - b))
    if a_num <= n:
        return True
    return False

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

left = 0
right = 10000000000

while (right - left) > 1:
    middle = (left + right) // 2
    if calc(middle):
        right = middle
    else:
        left = middle
print(right)

Submission status: Accepted

Solution code:
n,a,b=[int(j) for j in input().split()]
s=a-b
h=[]
for i in range(n):
    p=int(input())
    h.append(p)
h.sort()
import bisect
import math
def f(m):
    n=bisect.bisect_right(h,m*b)
    l=h[n:]
    c=0
    for i in range(len(l)):
        if l[i]-m*b/s>0:
            c+=math.ceil((l[i]-m*b)/s)
    if c<=m:
        return True
    else:
        return False
        


left=0
right=10**15
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        right=mid   #ここがleftならansもleft。
    else:
        left=mid
print(right)

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,*H=map(int,open(0).read().split())
l,r=0,10**9
while r-l>1:
	x=0;m=(l+r)//2
	for h in H:
		x-=min(0,(h-m*b)//(b-a))
	if x>m:
		l=m
	else:
		r=m
print(r)

Submission status: Accepted

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

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)

def check(m):
    m2 = m
    for i in range(n):
        if h[i] <= b * m:
            continue
        m2 -= math.ceil((h[i] - b * m) / (a - b))
        if m2 < 0:
            return False
    return True

l, r = 0, sum(h)//b+1
while r - l > 1:
    mid = (r + l) // 2
    # print(l, r, mid, check(mid))
    if check(mid):
        r = mid
    else:
        l = mid

print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    if a + b >= 10:
        print("error")
    else:
        print(a + b)
    return

#B
def B():
    s = S()
    if len(s) == len(set(s)):
        print("yes")
    else:
        print("no")
    return

#C
def C():
    n = II()
    m = inf
    ans = 0
    for _ in range(n):
        s = II()
        ans += s
        if s % 10:
            m = min(m, s)
    if ans % 10:
        print(ans)
    else:
        if m != inf:
            print(ans - m)
        else:
            print(0)
    return

# D
# 解説AC
# 解を2分探索で求める
# T回のときB*T以上の体力を持つ者に対しては(h-(B*T))/A-Bで最低必要な回数
# が求められることに気づけない
def D():
    def f(t):
        lh = list(map(lambda x: max(0, (x - b * t - 1) // (a - b) + 1), h))
        if sum(lh) <= t:
            return True
        return False
    n, a, b = LI()
    h = IR(n)
    maxh = max(h)
    ok = (maxh - 1) // b + 1
    ng = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok)
    return


#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
hs = []
for i in range(N):
  h = int(input())
  hs.append(h)
def check(n):
  s = 0
  for h in hs:
    if h > B*n:
      s += (h-B*n +A-B-1)//(A-B)
  return s <= n
a = 0
b = max(hs)//B+1
while a < b:
  i = (a + b)//2
  if check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b
print(r)

Submission status: Accepted

Solution code:

import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

n,a,b=getints()
hs=[getint() for _ in range(n)]
mx=max(hs)

min_cast = 0
max_cast = mx+1
c = a-b

hs = list(sorted(hs,reverse=True))

while min_cast < max_cast:
    cast = (min_cast + max_cast) // 2
    #values= list(filter(lambda s: s > 0, map(lambda s: s - b*cast, hs)))
    #need = sum(map(lambda v: (v + c - 1) // c, values))
    need = 0
    dec = b * cast
    for v in hs:
        v = v - dec
        if v <= 0:
            break
        need += (v + c - 1) // c
    if need <= cast:
        max_cast = cast
    else:
        min_cast = cast + 1

print(min_cast)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
INF = float("inf")


def solve(N: int, A: int, B: int, h: "List[int]"):
    tot = sum(h)

    def isOK(index):
        base = B*index
        sub = A-B
        counter = 0
        for hh in h:
            if hh > base:
                counter += int(math.ceil((hh-base)/sub))
            if index < counter:
                return False

        return index >= counter

    ng = -1
    ok = 2*tot//(N*B) + 1
    # print(ng, ok)

    while abs(ok - ng) > 1:
        mid = (ok + ng)//2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
    print(ok)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B, h)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def judge(m) :
    s = 0
    for i in range(N) :
        t = max(0, (h[i]-m*B+A-B-1)//(A-B))
        s += t
        if s > m :
            return False
    return True    

h.sort(reverse=True)
l, r = -1, 10 ** 9 + 1
while r - l > 1 :
    m = (l + r) // 2
    if judge(m) :
        r = m
    else :
        l = m

print(r)

Submission status: Accepted

Solution code:
import math

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

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

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

print(ok)

Submission status: Accepted

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

for _ in range(N):
    HP.append(int(input()))

left = 0
right = max(HP)

def canKill(count):
    ness = 0
    for hp in HP:
        ness += max(-(-(hp - B * count) // (A - B)), 0)
    if ness <= count:
        return True
    return False

while right - left > 1:
    middle = left + (right - left) // 2
    if canKill(middle):
        right = middle
    else:
        left = middle

print(right)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

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

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def check(h, x, A, B):
    h = [ hi - B * x for hi in h ]
    c = 0
    for hi in h:
        if hi <= 0:
            continue
        c += math.ceil(hi/(A-B))
    return c <= x

def main():
    N, A, B = l_inpl()
    h = line_inpl(N)

    l, r = 0, max(h)//B + 1000
    while l + 1 != r:
        mid = (l+r) // 2
        if check(h, mid, A, B):
            r = mid
        else:
            l = mid
    
    print(r)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
c=a-b
h_list=[int(input()) for i in range(n)]
l=0
r=(max(h_list)+b-1)//b
while r-l>1:
    m=(l+r)//2
    count=0
    for i in h_list:
        if i<=b*m:
            pass
        else:
            count+=((i-b*m)+c-1)//c
    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 _ in [0]*n]
c=a-b
from math import ceil

def b_search(a,b,value,lim):
    med=(a+b)//2
    if a==b:return a
    elif lim=="upper":
        if a+1==b:
            if value(b):return b
            else:return a
        elif value(med):return b_search(med,b,value,lim)
        else:return b_search(a,med-1,value,lim)
    else:
        if a+1==b:
            if value(a):return a
            else:return b
        elif value(med):return b_search(a,med,value,lim)
        else:return b_search(med+1,b,value,lim)
        
def value(x):
    return sum([max(ceil((i-x*b)/c),0) for i in h])<=x
    
print(b_search(1,10**9,value,"lower"))

Submission status: Accepted

Solution code:
def cond(arr,m):
  tmp=0
  for i in range(n):
    if m*b>=arr[i]:
      continue
    else:
      tmp+=(arr[i]-m*b+(a-b-1))//(a-b)
  if tmp<=m:
    return True
  else:
    return False

def bisect(l,r):
    while r-l!=1:
        m=(r+l)//2
        if cond(arr,m)==True:
            r=m
        else:
            l=m
    return r

n,a,b=map(int,input().split())
arr=[int(input()) for _ in range(n)]
print(bisect(-1,10**9+1))

Submission status: Accepted

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

def binary_search(l,r,func):
    if func(l):return l-1
    if not func(r):return r
    while l+1<r:
        i = (l+r)//2
        if func(i):
            r = i
        else:
            l = i
    return l

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

print(binary_search(0,10**9,f)+1)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
arr=[int(input()) for _ in range(n)]
l=0
r=10**9+1
while r-l!=1:
  tmp=0
  m=(l+r)//2
  for i in range(n):
    if m*b>=arr[i]:
      continue
    else:
      tmp+=(arr[i]-m*b+(a-b-1))//(a-b)
  if tmp<=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)]
lb, ub = 0, 10**9
while ub > lb + 1:
    mid = (lb + ub) // 2
    t, C, cnt = mid * B, A - B, 0
    for h in H:
        if h > t:
            tmp = h - t
            cnt += tmp // C + (tmp % C != 0)
            if cnt > mid:
                break
    if mid < cnt:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Accepted

Solution code:
def main():
    N, A, B = map(int, input().split())
    H = [int(input()) for _ in range(N)]
    left = 1
    right = max(H)
    while right - left > 1:
        t = (right + left) // 2
        c = 0
        for h in H:
            x = h - B * t
            if 0 >= x:
                continue
            c += x // (A - B)
            if x % (A - B):
                c += 1
        if c > t:
            left = t
        else:
            right = t
    print(right)


main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

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

def binarysearch(): #二分探索
    def isOK(y): #判定関数（個別に書き換え）
        res = 0
        for hi in h:
            hi -= b*y
            if hi <0: continue
            res += (hi+a-b-1)//(a-b)
        return res <= y
        
    ng = 0; ok = 10**9

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

print(binarysearch())

Submission status: Accepted

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


def check(n):

    c = 0
    for i in range(N):
        a = H[i] - n*B
        if a > 0:
            c += (a//(A-B)) + 1

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


l,h = 0,10**20
for _ in range(200):
    m = ((l+h)*0.5)
    if check(m):
        h = m
    else:
        l = m
import math
print(math.ceil(m))

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
h = [int(input()) for _ in range(n)]
d = a-b
l = 0
r = 10**10+1
ans = r


def check(num):
    global h
    global d
    global b
    cnt = 0
    for i in h:
        if i>b*num:
            cnt+= (i-b*num+d-1)//d
    return cnt<=num


while r>=l:
    mid = (r+l)//2
    if check(mid):
        r = mid-1
        ans = min(ans,mid)
    else:
        l = mid+1
print(ans)

Submission status: Accepted

Solution code:
import math

def ok_check(half, data, num, a, b):
    kari = 0
    for i in range(num):
        nokori = data[i] - half * b
        if nokori > 0:
            kari += math.ceil(nokori / (a - b))
    if kari > half:
        return 0
    else:
        return 1

def check(left, right, data, num, a, b):
    if left == right - 1:
        print(right)
        return
    half = (left + right) // 2
    if ok_check(half, data, num, a, b):
        check(left, half, data, num, a, b)
    else:
        check(half, right, data, num, a, b)

def main():
    num, a, b = map(int, input().split())
    data = [int(input()) for i in range(num)]

    left = 0
    right = max(data) // b + 1
    check(left, right, data, num, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter
import math
import copy
import collections
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def judge(x):
  res = np.ceil((hp - B*x)/(A-B))
  cnt = res[res > 0].sum()
  if cnt <= x:
    return True
  else:
    return False

# 二分探索 #
def nibutan(n):
  left = 0
  right = n
  while left+1 != right:
    middle = (left+right)//2
    if judge(middle):
      right = middle
    else:
      left = middle
  return right

N,A,B = IL()
hp = np.array([I() for i in range(N)])
hp.sort()
n = hp[-1]//B+1

ans = nibutan(n)

print(ans)

Submission status: Accepted

Solution code:
import math

def hersCode(N):
  ng = -1
  ok = N
  while ok -  ng > 1:
    mid = (ok + ng) // 2
    if judge(mid):
      ok = mid
    else:
      ng = mid
  return ok

def judge(x):
  cnt = 0
  for i in h:
    cnt += max(0, math.ceil((i - x * B) / (A - B)))
  return cnt <= x


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

print(hersCode(10 ** 9))

Submission status: Accepted

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

def test(n):
    x = H - n*B
    x[x<0] = 0
    return np.ceil(x/(A-B)).sum() <= n

left = 0
right = 10**9

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

Submission status: Accepted

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

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

l = 0
r = 0
for h in H:
    r = max(ceil(h/B),r)

while l != r-1:
    mid = (l+r)//2
    if attack(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 attack(n):
    s = 0
    for h in H:
        h -= B*n
        if h > 0:
            s += ceil(h/(A-B))
    return s <= n

l = 0
r = 0
for h in H:
    r = max(ceil(h/B),r)

for _ in range(30):
    mid = (l+r)//2
    if attack(mid):
        r = mid
    else:
        l = mid

print(r)

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)
s = 0
l = H[0]//B + 1
while l - s > 1:
    cnt = 0
    mid =(s+l) // 2
    x = mid*B
    for h in H:
        if h > x:
            cnt += math.ceil((h-x)/(A-B))
        else:
            break
    if cnt > mid:
        s = mid
    else:
        l = mid
print(l)

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)]
H.sort(reverse=True)
h=10**9
l=1
def check(t,a,b):
    c=b*t
    for i in H:
        if(i-c<=0):
            return True
        else:
            t+=(c-i)//(a-b)
            if(t<0):
                return False
    return True
while h!=l:
    t=(h+l)//2
    if(check(t,a,b)):
        h=t
    else:
        l=t+1
print(h)

Submission status: Accepted

Solution code:
def check(n, H, A, B):
    s = 0
    for h in H:
        s += max(-(-(h - n*B) // (A-B)), 0)
    if s <= n:
        return True
    else:
        return False


def main():
    N, A, B = map(int, input().split())
    H = [int(input()) for _ in range(N)]
    left = 0
    right = int(1e9)
    while left < right:
        center = (left + right) // 2
        if check(center, H, A, B):
            right = center
        else:
            left = center + 1
    print(left)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: int, B: int, h: "List[int]"):
    def can(n, A, B, a):
        tmp = 0
        base = B * n
        diff = A - B
        for v in a:
            rest = v - base
            if rest > 0:
                tmp += (rest - 1) // diff + 1
        if tmp <= n:
            return True
        return False
    h.sort(reverse=True)
    mx = h[0]
    l = 0
    r = (mx - 1) // B + 1
    while r - l > 1:
        m = (r + l) // 2
        if can(m, A, B, h):
            r = m
        else:
            l = m
    #print(l, r)
    ret = r
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, B, h)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def bsearch_int(init_ng, init_ok, cond):
    ng = init_ng
    ok = init_ok
    while(abs(ok - ng) > 1):
        mid = math.floor(abs(ok + ng)/2)
        if cond(mid):
            ok = mid
        else:
            ng = mid
    return ok

def condition(cnt, N, A, B, hs):
    basedmg = B*cnt
    diff = A - B
    diffcnt = 0
    for h in hs:
        if h < basedmg:
            break
        else:
            diffcnt += math.ceil((h-basedmg)/diff)
    if diffcnt > cnt:
        return False
    else:
        return True

import functools
def resolve():
    N, A, B = list(map(int, input().split(" ")))
    hs = [int(input()) for i in range(N)]
    hs.sort(reverse=True)
    print(bsearch_int(0, math.ceil(hs[0]/B), functools.partial(condition, N=N, A=A, B=B, hs=hs)))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from math import ceil
N,A,B=map(int,input().split())
H=[]
d=A-B
for i in range(N):
    h=int(input())
    H.append(h)
b=ceil(max(H)/B)
a=0
while(a!=b):
    m=a+(b-a)//2
    t=0
    for h in H:
        t+=ceil(max(h-B*m,0)/d)
    if t<=m:
        b=m
    else:
        a=m+1
print(a)

Submission status: Accepted

Solution code:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


def bisect_left_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


N, A, B = list(map(int, sys.stdin.readline().split()))
H = [int(sys.stdin.readline()) for _ in range(N)]
H = np.array(H)


def can_clear(count):
    # 倒せるなら 1、倒せないなら 0
    # 爆発の回数を決めたときにそれぞれ何回中心に選べばいいか
    center_counts = np.maximum(0, np.ceil((H - count * B) / (A - B)))
    return int(center_counts.sum() <= count)


cnt = bisect_left_callable(can_clear, 1, lo=1, hi=10 ** 10)
print(cnt)

Submission status: Accepted

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

def check(T):
    t = 0
    for i in range(N):
        if lst[i] > B * T:
            t += max((lst[i]-B*T + (A-B-1))//(A-B), 0)
        else:
            pass
    return t <= T

la = -1
ua = 10 ** 9
ans = 10 ** 9
while ua - la > 1:
    mid = (la + ua)//2
    if check(mid):
        ans = min(ans, mid)
        ua = mid
    else:
        la = mid
print (ans)

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

MAX=max(H)//B+1
MIN=min(H)//A

SA=A-B

while MAX!=MIN:
    
    x=(MAX+MIN)//2
    REST=[]

    for h in H:
        if h-B*x>0:
            REST.append(h-B*x)

    ANS=0
    #print(MAX,MIN,x,ANS)
    for r in REST:
        ANS+=-(-r//SA)

        if ANS>x:
            MIN=x+1
            break
    else:
        MAX=x

print(MAX)

Submission status: Accepted

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

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

L.sort()

ans = (L[-1] // B) + 1

def f(n):
    c = n
    for v in L:
        if v > n * B:
            v -= n * B
            t = v // (A - B)
            if v % (A - B) != 0:
                t += 1
            c -= t
    return c >= 0

first = 1
for _ in range(40):
    t = (first + ans) // 2
    if f(t):
        ans = t
    else:
        first = t

print(ans)

Submission status: Accepted

Solution code:
import math

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

left, right = 0, math.ceil(max(h)/B)
AB = A - B

while left+1 < right:
    mid = math.ceil((left + right) / 2)

    h_ = list(filter(lambda x: x > 0, [n - mid*B for n in h]))

    if sum([math.ceil(n / AB) for n in h_]) <= mid:
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
import numpy as np

N, A, B = list(map(int, input().split()))
h = np.array([int(input()) for i in range(N)], dtype='int64')

left, right = 0, np.ceil(np.max(h)/B)

while left+1 < right:
    mid = np.ceil((left + right) / 2)
    x = h - mid*B
    x[x<0] = 0
    x = np.ceil(x / (A - B))

    if np.sum(x) <= mid:
        right = mid
    else:
        left = mid

print(int(right))

Submission status: Accepted

Solution code:

import math
n,a,b = map(int, input().split())

m = [0] * n
for i in range(n):
  m[i] = int(input())
  

m.sort()


def enough(m,a,b,T):
  cnt = 0
  for hp in m:
    if hp > b*T:
      cnt += int(math.ceil((hp - b*T)/(a-b)))
      
  return True if  cnt <= T else False

r = 10**10
#r = 30
l = 0
mid = 0

while r - l > 1:
  mid = (r+l)//2
  if enough(m,a,b,mid) == True:
    r = mid
    #print("r:",r)
  else:
    l = mid
    #print("l:",l, " r:",r)

print(r)

Submission status: Accepted

Solution code:
from numpy import*
def main():
  t,*h=open(0)
  _,a,b=int32(t.split())
  h=int32(h)
  i,j=0,2**30
  while~i+j:
    k=(j+i)//2
    t=(b*k-h)//(a-b)
    if-k>sum(t[t<0]):i=k
    else:j=k
  print(j)
main()

Submission status: Accepted

Solution code:
from numpy import*
def main():
  _,a,b,*h=map(int,open(0).read().split())
  h=int32(h)
  i,j=0,2**30
  while~i+j:
    k=(j+i)//2
    t=(b*k-h)//(a-b)
    if-k>sum(t[t<0]):i=k
    else:j=k
  print(j)
main()

Submission status: Accepted

Solution code:
def main():
  from numpy import int32,sum
  _,a,b,*h=map(int,open(0).read().split())
  h=int32(h)
  i,j=0,2**30
  while~i+j:
    k=(j+i)//2
    t=(b*k-h)//(a-b)
    if-k>sum(t[t<0]):i=k
    else:j=k
  print(j)
main()

Submission status: Accepted

Solution code:
from numpy import*
t,*h=open(0)
_,a,b=int32(t.split())
h=int32(h)
i,j=0,2**30
while~i+j:
  k=(j+i)//2
  t=(b*k-h)//(a-b)
  if-k>sum(t[t<0]):i=k
  else:j=k
print(j)