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: Time Limit Exceeded

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

alive=[i for i in h if i > 0]
t=0

while (alive):
    boss=h.index(max(h))
    h=[i-B for i in h]
    h[boss]=h[boss]+B-A
    t+=1
    alive=[i for i in h if i > 0]

print(t)

Submission status: Time Limit Exceeded

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

cnt = 0
def atack(H):
 global cnt
 HA = [H[0] + A]
 HB = [i + B for i in H[1:]]
 H = HA + HB
 heapq.heapify(H)
 cnt += 1
 return H

while H[0] < 0:
 H = atack(H)

print(str(cnt))

Submission status: Time Limit Exceeded

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

counter=0
for i in range(max(H)):
    H.sort(reverse=True)
    if H[0]<=0:
        break
    counter=counter+1
    for j in range(N):
        if j==0:
            H[j]=H[j]-A
        else:    
            H[j]=H[j]-B
print(counter)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N, A, B = ILI()
    h = [II() for __ in range(N)]
    return (N, A, B, h)


def solve(N, A, B, h):
    mons = []
    for i in h:
        heapq.heappush(mons, -i)
    dif_ab = A - B
    count = 0
    while True:
        mons_max = -heapq.heappop(mons)
        if mons_max <= count * B:
            ans = count
            break
        else:
            heapq.heappush(mons, -(mons_max - dif_ab))
            count += 1

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,A,B = map(int,raw_input().split())
monsters = [0 for _ in xrange(N)]
for i in xrange(N):
    monsters[i] = int(raw_input())
cnt = 0
while(True):
    m = max(monsters)
    if m <=0:
        break
    midx = monsters.index(m)
    #print midx
    monsters[midx] -= A
    #print monsters
    
    for i in xrange(N):
        if i != midx:
            monsters[i] -= B
    cnt += 1
print cnt

Submission status: Time Limit Exceeded

Solution code:
import sys
N,A,B=map(int,input().split())
h=[]
for i in range(N):
  h+=[int(input())] 
count=0
C=A-B

while True:
  h.sort(reverse=1)
  if h[0]<=0:
    print(count)
    sys.exit()
  else:
    h[0]-=A
    for i in range(N-1):
      h[i+1]-=B
    count+=1

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
  N,A,B = i_map()
  h = [i_input() for i in range(N)]

  def check(mid,A,B):
    cnt = 0

    for i in h:
      i -= B*mid
      if i <= 0:
        continue
      cnt += math.ceil(i/(A-B))
    if cnt <= mid:
      return True
    else:
      return False

  start = 1
  end = max(h)

  while end - start > 1:
    middle = (end + start)//2
    if check(middle,A,B):
      end = middle
    else:
      start = middle

  print(end)



if __name__=="__main__":
    main()

Submission status: Accepted

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

def ba(s):
    count = 0
    for i in h_list:
        i -= s*b
        if i > 0:
            count += -(-i//(a-b))
    if count <= s:
        return True
    else:
        return False


ng = 0
ok = 10**9
while ok  > ng +1 :
    mid = (ng+ok)//2
    if ba(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

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

def can_terminate(x):
  count = 0
  for monster in monsters:
    count += max(0, math.ceil((monster-B*x)/(A-B)))
  return count <= x

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

Submission status: Accepted

Solution code:
# 決め打ち二分探索
# 全員にBダメージ、その後1体選んで(A-B)ダメージと読み替える（対称性の確保。lesson.md参照）
# あとはk回以下で倒せるかを計算して二分探索
# Gluttonyと同様の構造なので、あちらと同様にTLEには注意して書くこと

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

additional = a - b

def feasible(k):
    additional_num = sum([max((hp-(b*k) + additional - 1) // additional, 0) for hp in hitpoints])
    return additional_num <= k

ok = 10**9+1
ng = 0

# めぐる式二分探索
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if feasible(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import math
N, A, B = map(int, input().split())
all_attack = 0
enemy = [int(input()) for i in range(N)]


def possible_kill_all(attack):
    tmp_enemy = [v-B*attack for v in enemy]
    tmp_needed_attack = 0
    for v in tmp_enemy:
        if v>0:
            tmp_needed_attack += math.ceil(v/(A-B))
    if tmp_needed_attack <= attack:
        return True
    else:
        return False



possible = 10**14
impossible = 0

while possible - impossible > 1:
    M = (possible+impossible)//2
    if possible_kill_all(M):
        possible = M
    else:
        impossible = M

print(possible)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
l=[int(input())for i in range(n)]
a-=b
def  enough(x):
    return sum(max((h-b*x+a-1)//a,0) for h in l)<=x
#(ng,ok]type
ok,ng=10**9,-1
# [ok,ng)type->eraseng,ok=ok,ng
eps=10**(-10)
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if enough(mid):ok=mid
    else:ng=mid
print(ok)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
import random
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, A, B = read_values()
    V = [int(input()) for _ in range(N)]
    K = A - B
    l = 0
    r = max((v - 1) // B + 1 for v in V)
    while l < r - 1:
        m = (l + r) // 2

        t = 0
        for v in V:
            u = v - m * B
            t += max(0, (u + K - 1) // K)
        
        if t > m:
            l = m
        else:
            r = m
    
    print(r)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n, a, b = map(int, input().split())
h = []
for _ in range(n):
    h.append(int(input()))

def solve(e):
    cnt = 0
    for i in h:
        if i<=b*e:
            continue
        cnt += (i-b*e+a-b-1)//(a-b)
    return cnt<=e

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, A, B, H):
    c = A-B
    def f(n):
        m = n
        for h in H:
            h -= n * B
            if h > 0:
                m -= -(-h // c)
        return 1 if m >= 0 else 0

    return Bisect(f).bisect_left(1, 0, 10**9)



def main():
    N, A, B = read_int_n()
    H = [read_int() for _ in range(N)]
    print(slv(N, A, B, H))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

l = 0
r = 10**9

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

    count = 0#Aの処理(A-B)を余ったところに適用していく
    for i in range(N):
        count += max(0,h[i]-B*tmp)//(A-B)
        if max(0,h[i]-B*tmp)%(A-B) != 0:
            count+=1
    
    if tmp >= count:
        r = tmp
    else:
        l=tmp

print(r)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

h.sort()
d = A - B

ng = (h[-1] + (A - 1)) // A - 1
ok = (h[-1] + (B - 1)) // B
while ok - ng > 1:
    m = (ok + ng) // 2
    b = B * m
    if m >= sum((h[i] - b + (d - 1)) // d for i in range(bisect_right(h, b), N)):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Accepted

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

diff = A - B #追加ダメージ
T = (max(H)+B-1)//B #答えはT以下

def clearable(t): #t回以内で敵を全滅できるか判定
    Higher = [h-B*t for h in H if h-B*t > 0]
    return True if sum([(h+diff-1)//diff for h in Higher]) <= t else False

def binary_search(a, b, judge): #b must be a or higher
    if a == b:
        return a, b
    
    c = a + (b - a)// 2
    return (a, c) if judge(c) else (c+1, b)

a, b = 0, T
while a != b:
    a, b = binary_search(a, b, clearable)
print(a)

Submission status: Accepted

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

ok=10**9
ng=0

while ok-ng>1:
    cen=(ok+ng)//2
    cnt=0

    for hh in h:
        hh-=b*cen

        cnt+=max(0,(hh+c-1)//c)
    
    if cnt<=cen:
        ok=cen
    else:
        ng=cen

print(ok)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, A, B = LI()
    H = []
    for _ in range(N):
        H.append(I())
    ng = -1
    ok = 10**9 + 1

    def enough(n, H):
        diff = A - B
        num = 0
        for i in range(N):
            H[i] -= B * n

        for i in range(N):
            if H[i] <= 0:
                continue
            num += H[i] // diff
            if H[i] % diff > 0:
                num += 1
        return num <= n

    while ok - ng > 1:
        attack = (ok + ng) // 2
        if enough(attack, H.copy()):
            ok = attack
        else:
            ng = attack

    print(ok)



main()

Submission status: Accepted

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


def calc(num, a):
    cnt = 0
    for i, h in enumerate(a):
        x = h - num * B
        x = (x - 1) // (A - B) + 1
        if x > 0:
            cnt += x
    if cnt <= num:
        return True
    else:
        return False


start = 0
end = 10 ** 10

while end - start > 1:
    mid = (start + end) // 2
    if calc(mid, H[:]):
        end = mid
    else:
        start = mid

print(end)

Submission status: Accepted

Solution code:
import numpy as np

N, A, B = map(int, input().split())
H = np.zeros(shape=N, dtype='int64')
for _ in range(N):
    h = int(input())
    H[_] = h


def calc(num, a):
    a -= num * B
    a = (a - 1)//(A - B) + 1
    if sum(a[a > 0]) <= num:
        return True
    else:
        return False


start = 0
end = 10 ** 10

while end - start > 1:
    mid = (start + end) // 2
    if calc(mid, H.copy()):
        end = mid
    else:
        start = mid

print(end)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10**9


def main():
    N, A, B = in_nn()
    diff = A - B
    h = list(in_all())

    def is_ok(mid):

        cnt = 0
        for i in range(N):
            x = h[i] - mid * B
            if x > 0:
                cnt += (x + diff - 1) // diff

        return cnt <= mid

    def binary_search(ng, ok):

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

    ans = binary_search(0, INF + 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def abc063_d():
    n, a, b = map(int, input().split())
    H = [int(input()) for _ in range(n)]
    lower, upper = 0, 10**16
    d = a - b
    while upper - lower > 1:
        x = (upper + lower) // 2
        v = 0
        for hi in H:
            v += (max(0, hi - x*b) + d - 1) // d
            if v > x: break
        if v <= x: upper = x
        else: lower = x
    print(upper)

if __name__ == '__main__':
    abc063_d()

Submission status: Accepted

Solution code:
def abc063_d():
    n, a, b = map(int, input().split())
    H = [int(input()) for _ in range(n)]
    lower, upper = 0, 10**16
    d = a - b
    while upper - lower > 1:
        x = (upper + lower) // 2
        v = 0
        for hi in H:
            v += (max(0, hi - x*b) + d - 1) // d
        if v <= x: upper = x
        else: lower = x
    print(upper)

if __name__ == '__main__':
    abc063_d()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline

def baku(x):
    g = h - b*x
    g = g[g>0]
    g += a-b-1
    g //= a-b
    if sum(g) <= x:
        return True
    else:
        return False

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

lb = 0
ub = 10**9 + 1
while ub - lb > 1:
    x = (ub+lb) //2
    if baku(x):
        ub = x
    else:
        lb = x
print(ub)

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
H = [int(input()) for _ in range(N)]
ok = 10**9
ng = 0
while ng + 1 < ok:
    c = ok + ng >> 1
    G = [max(0, h-c*B) for h in H]
    n = sum(-(-g//(A-B)) for g in G)
    if c >= n:
        ok = c
    else:
        ng = c
print(ok)

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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

# binary search
sum_h = sum(h)

left = sum_h // (a + b*(n-1))
right = min([sum_h//a + n, max(h)//b + 1])

while left < right:
    center = (left + right) // 2

    base = center * b
    num = 0
    for i in h:
        i -= base
        if i > 0:
            num += (i - 1) // (a - b) + 1

    if num <= center:
        right = center
    else:
        left = center + 1

print(left)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))
ac = (max(h) - 1) // b + 1
wa = 0
while ac - wa > 1:
    wj = (ac + wa) // 2
    num = 0
    for i in range(n):
        num += max((h[i] - b * wj - 1) // (a - b) + 1, 0)
    if num <= wj:
        ac = wj
    else:
        wa = wj
print(ac)

Submission status: Accepted

Solution code:
import heapq

n, a, b = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))
ac = (max(h) - 1) // b + 1
wa = 0
while ac - wa > 1:
    wj = (ac + wa) // 2
    num = 0
    for i in range(n):
        num += max((h[i] - b * wj - 1) // (a - b) + 1, 0)
    if num <= wj:
        ac = wj
    else:
        wa = wj
print(ac)

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 det(m):
  C = [max(0, a-B*m) for a in h]
  #print(m, C)
  if sum([math.ceil(b/(A-B)) for b in C]) > m:
    return False
  else:
    return True
  
l = 0
r = math.ceil(max(h)/A*N)
#print(l, r)
while r - l > 1:
  c = (l + r) // 2
  if det(c):
    r = c
  else:
    l = c
    
print(r)

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
H = [int(input()) for n in range(N)]
L = 0
R = 10**9

while 1<R-L:
  m = (L+R)//2
  if m<-sum(min(0,(h-m*B)//(B-A)) for h in H):
    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)]

def check(k):
  cnt = 0
  for i in range(N):
    cnt += max(0, math.ceil((h[i] - B*k) / (A - B)))
  if cnt <= k:
    return 1
  else:
    return 0

y, n = 10**10, 0
while y-n > 1:
  k = (y+n)//2
  if check(k):
    y = k
  else:
    n = k

print(y)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, A, B = map(int, readline().split())
H = list(map(int,read().split()))
H = sorted(H,reverse = True)
t = A-B

def solve(x):
    cnt = 0
    for i in range(N):
        rem = H[i]-x*B
        if rem <= 0:
            break
        else:
            cnt += -(-rem // t)
    if cnt <= x:
        return True
    else:
        return False 
    

left = 0
right = 10**9
while right - left > 1:
    x = (left + right) // 2
    flag = solve(x)
    if flag:
        right = x
    else:
        left = x
        
print(right)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, A, B = map(int, readline().split())
H = list(map(int,read().split()))
H = sorted(H,reverse = True)
t = A-B

def solve(x):
    cnt = 0
    for i in range(N):
        rem = H[i]-x*B
        if rem <= 0:
            break
        else:
            cnt += -(-rem // t)
    if cnt <= x:
        return True
    else:
        return False 
    

left = 0
right = 10**9+5
while right - left > 1:
    x = (left + right) // 2
    flag = solve(x)
    if flag:
        right = x
    else:
        left = x
        
print(right)

Submission status: Accepted

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

for i in range(N):
  h=int(input())
  H.append(h)
def isok(k):
  I=H
  I=[i-B*k for i in H]
  count=0
  for i in range(N):
    if I[i]>0:
      count+=math.ceil(I[i]/(A-B))
  if count<=k:
    return True
  else:
    return False

start=0
end=sum(H)//B
while end-start>1:
  mid=(start+end)//2
  if isok(mid):
    end=mid
  else:
    start=mid
print(end)

Submission status: Accepted

Solution code:

from math import ceil
def resolve():
    def chick(k):
        cnt = 0
        for i in range(N):
            h = ceil((H[i] - B * k) / (A - B))
            cnt += max(0, h)
        return cnt <= k

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

    # 最小の攻撃回数を求める
    # 魔法攻撃の回数をkとした時、すべての魔物は少なくともkBの体力が削られている
    # H[i] - kB > 0 であるような各iについて、その敵に対してA-Bの攻撃を何回当てれば体力が0になるかが算出される。
    # 上記の計算：(H[i] - kB) / (A-B) (ただし切り上げ)を計算して和を取る
    ok = 10 ** 10
    ng = 0
    while ok - ng > 1:
        k = (ok + ng) // 2
        if chick(k):
            ok = k
        else:
            ng = k

    print(ok)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, a, b = ns()

    h = [ni() for _ in range(n)]

    upper = 10 ** 9
    lower = 0

    while upper - lower > 1:
        mid = (upper + lower) // 2
        cnt = 0
        for hi in h:
            cnt += int(math.ceil(max(0, hi - b * mid) / (a - b)))
        if cnt <= mid:
            upper = mid
        else:
            lower = mid
    print(upper)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def is_ok(arg):
  # 条件を満たすかどうか？問題ごとに定義
  cnt = 0
  C = A-B
  for h in H:
    wk = h - B*arg
    if wk<0:
      continue
    else:
      cnt += (wk+C-1) // C
  return cnt <= arg

def meguru_bisect(ng, ok):
  '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
  '''
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return ok

ng = 0
ok = 10**16

print(meguru_bisect(ng,ok))

Submission status: Accepted

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

Submission status: Accepted

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

ok = 1000000000
ng = 0

while ok != ng+1:
    mid = (ok+ng)//2
    range_damage = mid*B
    attack_count = 0
    for value in H:
        if range_damage < value:
            if (value - range_damage)%(A-B)==0:
                attack_count += (value - range_damage)//(A-B)
            else:
                attack_count += 1+(value - range_damage)//(A-B)

    if attack_count <= 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 solve(k):
    cnt = 0
    for i in range(N):
        if H[i] > B * k:
            cnt += (H[i] - B * k - 1) // (A - B) + 1
    return cnt <= k


left = 0
right = 10 ** 9 + 1

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

print(right)

Submission status: Accepted

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


ok, ng = 10**10, 0
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    ok_flag = True
    cnt = 0
    for h in hl:
        rem = h - mid*b
        if rem > 0:
            need = (rem-1)//(a-b) + 1
        else:
            need = 0
        cnt += need
    # ...
    if cnt <= mid:
        ok = mid
    else:
    	ng = mid
print(ok)

Submission status: Accepted

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

l = (min(h_s) - 1) // a + 1
r = (max(h_s) - 1) // b + 1

c = a - b
while l != r:
    pos = (l + r) // 2
    cnt = 0
    base = b * pos
    for h in h_s:
        rem = h - base
        cnt += max(0, (rem - 1) // c + 1)
    if cnt <= pos:
        r = pos
    else:
        l = pos + 1
print(r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def judge(x):
    cnt = 0
    
    for hi in h:
        cnt += max(0, (hi-B*x+A-B-1)//(A-B))
    
    return cnt<=x

def binary_search():
    l, r = 0, 10**10
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

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

Submission status: Accepted

Solution code:
import sys
from math import ceil
def input(): return sys.stdin.readline().strip()


def main():
    N, A, B = map(int, input().split())
    monster = [int(input()) for _ in range(N)]
    additional = A - B
    """
    Bの誘爆を基本に考えて決めうち二分探索を行う。
    """
    left = 0
    right = max(monster) // B + 1
    while right - left > 1:
        mid = (left + right) // 2
        times = 0
        for m in monster:
            times += max(0, ceil((m - B * mid) / additional))
        if times > mid:
            left = mid
        else:
            right = mid
    print(right)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

#めぐる式二分探索
#indexが条件を満たすか判定
def isOK(index, H):
  now_min = index * B
  all_H = []
  for i in range(len(H)):
    if H[i] > now_min:
      all_H.append(H[i] - now_min)
  count = 0 
  for j in all_H:
    if j % (A - B) == 0:
      count += int(j // (A - B))
    else:
      count += int(j // (A - B)) + 1
  if count <= index:
    return True
  else:
    return False
  
#にぶたん
#A : 配列
def binary_search(H):
  N = 10 ** 9 + 1
  ng = -1
  ok = N
  while (abs(ok - ng) > 1):
    mid = int((ok + ng) / 2)
    if isOK(mid, H):
      ok = mid
    else:
      ng = mid
  return ok
  

print(binary_search(H))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def meguru_bisect(ok, ng):
        """
        is_okを定義して下さい
        :param ok: 取りうる最小の値-1
        :param ng: 取りうる最大の値+1
        :return: is_okを満たす最小(もしくは最大)の値
        """
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    def is_ok(x):
        cnt = 0
        for h in H:
            h -= b * x
            if h > 0:
                cnt += (h + ab - 1) // ab
        return cnt <= x

    n, a, b = map(int, input().split())
    ab = a - b
    H = list(int(input()) for _ in range(n))

    res = meguru_bisect(10 ** 9 + 1, 0)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n,a,b = map(int,ipt().split())
    h = [int(ipt()) for i in range(n)]
    l = 1
    r = 10**10
    while l != r:
        mid = l + (r-l)//2
        nm = 0
        for i in h:
            nm += max(0,math.ceil((i-b*mid)/(a-b)))
        if nm > mid:
            l = mid+1
        else:
            r = mid

    print(l)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
def is_ok(mid):
  ind=bisect.bisect_right(h,mid*b)
  cnt=0
  for i in range(ind,n):
    cnt+=(h[i]-mid*b+a-b-1)//(a-b)
  if cnt<=mid:return True
  else:return False
n,a,b=map(int,input().split())
h=sorted([int(input()) for _ in range(n)])
ng=-1
ok=(h[-1]+b-1)//b
while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if is_ok(mid):ok=mid
  else:ng=mid
print(ok)