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:
#!/usr/bin/env python3
import sys
from math import ceil

def solve(N: int, A: int, B: int, h: "List[int]"):
    INF = 10000000000
    
    def f(K: int):
        c = 0
        for i in range(N):
            c += ceil(max(0, h[i] - B*K)/(A-B))

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


    def binary_search(ok: int, ng: int):
        while ok-ng > 1:
            mid = (ok+ng)//2
            if f(mid):
                ok = mid
            else:
                ng = mid
        return ok

    # def b(ok: int, ng: int):
        
    #     while ok-ng > 1:
    #         mid = (ok+ng)//2
    #         if f(mid):
    #             ok = mid
    #         else:
    #             ng = mid

    #     return ok

    print(binary_search(INF, 0))

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
#!/usr/bin/env python3
import sys
from math import ceil

def solve(N: int, A: int, B: int, h: "List[int]"):
    INF = 10000000000
    
    def f(K: int):
        c = 0
        for i in range(N):
            c += ceil(max(0, h[i] - B*K)/(A-B))

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


    def b(ok: int, ng: int):
        
        while ok-ng > 1:
            mid = (ok+ng)//2
            # print(ok, ng, mid)  
            if f(mid):
                ok = mid
            else:
                ng = mid

        return ok

    print(b(INF, 0))

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, a, b = list(map(int, input().rstrip('\n').split()))
    h = [int(input().rstrip('\n')) for _ in range(n)]

    cor_v = 10 ** 20
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for v in h:
            if v > bin_v * b:
                cost += (v - bin_v * b + (a - b) - 1) // (a - b)
        #costが制約を満たすか
        if cost <= bin_v:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from math import ceil
from bisect import bisect

n, a, b = map(int, input().split())
raw_hs = [int(input()) for _ in range(n)]
hs = sorted(raw_hs, reverse=True)
diff = a - b

c_min = 0
c_max = int(10e9)

while c_max - c_min > 1:
	c = (c_min + c_max) // 2
	tmp_hs = [h - c * b for h in hs]
	rem = sum([ceil(h / diff) for h in tmp_hs if h > 0])
	if rem > c:
		c_min = c
	else:
		c_max = c

print(c_max)

Submission status: Accepted

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

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

while hi-lo > 1:
    mi = (hi+lo)//2
    rest = 0
    for i in range(n):
        rest += max(0,-(-(H[i]-b*mi)//(a-b)))
    if rest <= mi:
        hi = mi
    else:
        lo = mi
        
print(hi)

Submission status: Accepted

Solution code:
import math

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


def chk(k):
    a_cnt = 0
    for h in H:
        tmp = h - B * k
        if tmp > 0:
            a_cnt += math.ceil(tmp / (A - B))
    return k >= a_cnt


def find(l, r):
    if l > r: return l
    m = (l + r) // 2
    if chk(m):
        r = m - 1
    else:
        l = m + 1
    return find(l, r)


print(find(0, 10 ** 9))

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, a, b = list(map(int, input().rstrip('\n').split()))
    h = [int(input().rstrip('\n')) for _ in range(n)]
    ok = 10 ** 9
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        d1 = b * mid
        d2 = a - b
        cnt = 0
        for v in h:
            cnt += max((v - d1 + d2 - 1) // d2, 0)
        if cnt <= mid:
            ok = mid
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import ceil
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

n,a,b=map(int,input().split())
h=[]
for i in range(n):
    h.append(int(input()))
ok=inf
left=1
right=10**9+10
while left<right:
    mid=(left+right)//2
    tmp=0
    for hi in h:
        tmp+=max(0,ceil((hi-mid*b)/(a-b)))
    if tmp>mid:
        left = mid+1
    else:
        right=mid
        ok=min(ok,mid)
print(ok)

Submission status: Accepted

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

def can_kill(count):
    ness = 0
    for hp in h:
        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 can_kill(middle):
        right = middle
    else:
        left = middle

print(right)

Submission status: Accepted

Solution code:
from math import ceil 
n,a,b=map(int,input().split())
l=[int(input()) for i in range(n)]
def check(x):
    c=0
    l1=[i-b*x for i in l]
    for i in l1: 
         if i<=0:
             continue 
         c+=ceil((i)/(a-b))
    return c<=x
lo=0 
ans=-1 
hi=10**9+4 
while lo<=hi:
    mi=(lo+hi)>>1 
    if check(mi):
        ans=mi 
        hi=mi-1
    else:
        lo=mi+1 
print(ans)

Submission status: Accepted

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

def C(x):
    Y = [0] * N
    for i in range(N):
        Y[i] = X[i] - x * B
    
    cnt = 0
    for i in range(N):
        if Y[i] > 0:
            cnt += (Y[i] + A - B - 1) // (A - B)
    return cnt <= x

ng = 0; ok = 10**18
while ok - ng > 1:
    mid = (ng + ok) >> 1
    if C(mid): ok = mid
    else: ng = mid

print(ok)

Submission status: Accepted

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

def check(t):
    l=[]
    for i in h:
        i-=t*B
        if i > 0:
            l.append(i)
    if len(l) != 0:
        while t>=0:
            i=l.pop()
            t-=-(-i//(A-B))
            if (len(l)==0) and (t>=0):
                return True
        return False
    else:
        return True

min=0
max=hmax
while max != min + 1:
    j=(max-min)//2+min
    if check(j) == True:
        max = j
    else:
        min = j
print(max)

Submission status: Accepted

Solution code:
import sys
I = lambda:int(sys.stdin.readline())
LI = lambda:[int(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]

N,A,B = LI()
H = IR(N)

def isOK(c):
    cnt = 0
    for enc in H:
        if enc - B*c > 0:
            cnt += ((enc - B*c)+(A-B)-1)//(A-B)
            if cnt > c:
                return False
    return True

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

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
I = lambda:int(sys.stdin.readline())
LI = lambda:[int(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]

def check(a,b,h,c):
    cnt = 0
    for enc in h:
        if enc - b*c > 0:
            cnt += ((enc - b*c)+(a-b)-1)//(a-b)
            if cnt > c:
                return False
    return True


N,A,B = LI()
H = IR(N)

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

while(OK-NG>1):
    mid = (OK+NG)//2
    if check(A,B,H,mid):
        OK = mid
    else:
        NG = mid

print(OK)

Submission status: Accepted

Solution code:
import math
n, a, b = map(int, input().split())
list_enemy = [int(input()) for _ in range(n)]
list_enemy.sort(reverse=True)

diff_dam = a - b
min_a = math.ceil(list_enemy[-1] / a)
max_a = math.ceil(list_enemy[0] / b)
while max_a - min_a > 1:
  mid_a = min_a + (max_a - min_a) // 2
  count = 0
  for one_enemy in list_enemy:
    rest_h = one_enemy - (b * mid_a)
    if rest_h > 0:
      count += math.ceil(rest_h / diff_dam)
    else:
      break
  if count <= mid_a:
    max_a = mid_a
  else:
    min_a = mid_a
print(max_a)

Submission status: Accepted

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

def tansaku(x):
  cou = 0
  normal = b * x
  for hp in lis:
    r = hp -normal
    if r <= 0:continue
    cou += r // more
    
    if r % more != 0:
      cou += 1
  return cou <= x

left = 1
right = max(lis)
while right - left > 1:
  mid = (right + left)//2
  if tansaku(mid):
    right = mid
  else:
    left = mid
print(right)

Submission status: Accepted

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

def calc(x):
  bomb = 0
  for h in H:
    if h > B*x:
      bomb += ((h-B*x)-1)//(A-B) +1
  return (x >= bomb)

def check(a,b):
  mid = (a+b)//2
  if a == mid:
    return b
  if calc(mid):
    return check(a,mid)
  else:
    return check(mid,b)

print(check(0,10**9))

Submission status: Accepted

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

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

    def binary_search_meguru(Arr,N,A,B):
        left = -1
        right = 10**9 + 1
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(Arr,mid,N,A,B): right = mid
            else: left = mid
        return right
    
    print(binary_search_meguru(h,N,A,B))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    def binary_search_meguru(Arr,N,A,B):
        left = -1
        right = 10**10 + 1
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(Arr,mid,N,A,B): right = mid
            else: left = mid
        return right
    
    print(binary_search_meguru(h,N,A,B))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

def check(T):
    t = 0
    for h in H:
        h -= B*T
        if h > 0:
            t += math.ceil(h/(A-B))
    return T >= t

def main():
    lb = ub = 0
    for h in H:
        ub += h//B + 1

    while ub - lb > 1:
        mid = (lb + ub)//2
        if check(mid):
            ub = mid
        else:
            lb = mid

    print(ub)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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


def solve(bomb):
    count = 0
    for i in range(N):
        remain = H[i] - (B*bomb)
        # まだ残ってる場合、中心爆発分で追加ダメージが必要なのでカウントする
        if remain > 0:
            additional_damage = (A-B)
            c = -(-remain // additional_damage)
            count += c

    if count <= bomb:
        return True
    else:
        return False


# leftは条件を満たす値、rightは満たさない値
def meguru(left, right):
    while abs(left - right) > 1:
        mid = (left + right) // 2;

        if (solve(mid)):
            left = mid
        else:
            right = mid;

    return left


# 問題を「k回の爆発でクリアできるか」に置き換えれば、めぐる式二分探索が使える
print(meguru(max(H), 0))

Submission status: Accepted

Solution code:
import math

N,A,B = map(int,input().split())
H = [int(input()) for _ in range(N)]
INF = 10**9
cnt = 0

def check(K):
  tmp = 0
  for i in range(N):
    rem = H[i] - B * K
    if rem > 0:
      tmp += math.floor((rem + (A - B - 1)) / (A - B))
  return tmp <= K

def binary_search(ok,ng):
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if check(mid):
      ok = mid
    else:
      ng = mid
  return ok

print(binary_search(INF,0))

Submission status: Accepted

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


def check(k):
    return sum([(x - k * b + a - b - 1) // (a - b)
                for x in ls if x - k * b > 0]) <= k


m = max(ls)
lo = (m + a - 1) // a
hi = (m + b - 1) // b + 1
mi = (hi + lo) // 2
while hi > lo:
    mi = (hi + lo) // 2
    if check(mi):
        hi = mi
    else:
        lo = mi + 1
print(lo)

Submission status: Accepted

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


def check(k):
    return sum([(x - k * b + a - b - 1) // (a - b)
                for x in ls if x - k * b > 0]) <= k


m = max(ls)
lo = (m + a - 1) // a
hi = (m + b - 1) // b + 1
mi = (hi + lo) // 2
while hi > lo + 1:
    mi = (hi + lo) // 2
    if check(mi):
        hi = mi
    else:
        lo = mi
if check(lo):
    print(lo)
else:
    print(hi)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
ls = [int(input()) for _ in range(n)]
m = max(ls)
lo = (m + a - 1) // a
hi = (m + b - 1) // b + 1
mi = (hi + lo) // 2
while hi > lo + 1:
    mi = (hi + lo) // 2
    if sum([(x - mi * b + a - b - 1) // (a - b)
            for x in ls if x - mi * b > 0]) <= mi:
        hi = mi
    else:
        lo = mi
if sum([(x - lo * b + a - b - 1) // (a - b)
        for x in ls if x - lo * b > 0]) <= lo:
    print(lo)
else:
    print(hi)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
ls = [int(input()) for _ in range(n)]
m = max(ls)
lo = (m + a - 1) // a
hi = (m + b - 1) // b + 1
mi = (hi + lo) // 2
while hi > lo + 1:
    mi = (hi + lo) // 2
    if sum([(max(x - mi * b, 0) + a - b - 1) // (a - b) for x in ls]) <= mi:
        hi = mi
    else:
        lo = mi
if sum([(max(x - lo * b, 0) + a - b - 1) // (a - b) for x in ls]) <= lo:
    print(lo)
else:
    print(hi)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
ls = sorted([int(input()) for _ in range(n)])
lo = (ls[-1] + a - 1) // a
hi = (ls[-1] + b - 1) // b + 1
mi = (hi + lo) // 2
while hi > lo + 1:
    mi = (hi + lo) // 2
    if sum([(max(x - mi * b, 0) + a - b - 1) // (a - b) for x in ls]) <= mi:
        hi = mi
    else:
        lo = mi
if sum([(max(x - lo * b, 0) + a - b - 1) // (a - b) for x in ls]) <= lo:
    print(lo)
else:
    print(hi)

Submission status: Accepted

Solution code:
import math
monsterNum, centerDamage, otherDamage = map(int, input().split())
monsterHitpoint = [0] * monsterNum
maxHitpoint = 0

def enough(times):
  result = True
  damageCount = 0
  hitpoint = [monsterHitpoint[i] - otherDamage * times for i in range(monsterNum)]
  for i in range(monsterNum):
    if hitpoint[i] > 0:
      damageCount += math.ceil(hitpoint[i] / (centerDamage - otherDamage))
    if damageCount > times:
      result = False
      break
  return result
  
for i in range(monsterNum):
  monsterHitpoint[i] = int(input())
  if maxHitpoint < monsterHitpoint[i]:
    maxHitpoint = monsterHitpoint[i]
#2分探索
low, high = 0, math.ceil(maxHitpoint / otherDamage)
while low <= high:
  minTimes = (low + high) // 2
  checkEnough = enough(minTimes)
  if checkEnough and not(enough(minTimes - 1)):
    break
  elif checkEnough:
    high = minTimes - 1
  elif not checkEnough and (enough(minTimes + 1)):
    minTimes += 1
    break
  elif not checkEnough:
    low = minTimes + 1
print(minTimes)

Submission status: Accepted

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



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, a, b = LI()
L = IR(n)
ok = max(L) // b + 1
ng = 0
while ok > ng + 1:
    mid = (ok + ng) // 2
    remain = mid
    for i in range(n):
        remain -= max(0, (L[i] - b * mid) // (a - b) + bool((L[i] - b * mid) % (a - b)))
        if remain < 0:
            ng = mid
            break
    else:
        ok = mid



print(ok)

Submission status: Accepted

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

sum_h = sum(h)
sum_dam = B * N + (A - B)
ng = (sum_h - 1) // sum_dam + 1 - 1
ok = (max(h) - 1) // B + 1
ans = (ng + ok + 1) // 2
while ok - ng > 1:
    cnt = ans
    flag = 0
    for h_i in h:
        rem = h_i - B * ans
        if rem > 0:
            cnt -= (rem - 1) // (A - B) + 1
            if cnt < 0:
                flag = 1
                break
    if flag == 0:
        ok = ans
    else:
        ng = ans
    ans = (ng + ok + 1) // 2

print(ans)

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)
high = math.ceil(H[0] / B)
low = 0
while high > low+1:
    mid = (high+low) // 2
    cnt = 0
    for i in range(N):
        if H[i] - mid*B > 0:
            # 残りを減らすのに必要な回数を計上
            cnt += math.ceil((H[i] - mid*B)/(A - B))
        else:
            break
    # 残りを減らす回数がmidを超えているならその回数ではすべてを倒しきれない
    if cnt <= mid:
        high = mid
    else:
        low = mid

print(high)

Submission status: Accepted

Solution code:
from bisect import bisect

def solve(N, A, B, H, total, M):
    class Solver:
        def __init__(self, N, A, B, H, total):
            self.N = N
            self.B = B
            self.BA = A-B
            self.H = H
            self.len = idiv(total, B)

        def __getitem__(self, k):
            Bk = self.B * k
            cnt = 0
            for i in range(self.N):
                h = H[i] - Bk
                if h < 0:
                    continue
                cnt += idiv(h, self.BA)
                if cnt > k:
                    return -1
            #print("[%d]"%k, cnt, k)
            return 1 if cnt <= k else -1

        def __len__(self):
            return self.len

    k0 = idiv(total, (B*N+A))
    s = Solver(N, A, B, H, total)
    k = bisect(s, 0, k0, idiv(M, B))
    print(k)

def main():
    input = open(0).readline
    N, A, B = map(int, input().split())
    H = [0]*N
    M = 0
    total = 0
    for i in range(N):
        h = int(input())
        H[i] = h
        M = max(M, h)
        total += h
    solve(N, A, B, H, total, M)

def idiv(x, y):
    if x <= 0:
        return 0
    q, r = divmod(x, y)
    return q + (1 if r > 0 else 0)



main()

Submission status: Accepted

Solution code:
from bisect import bisect

def solve(N, A, B, H, total):
    class Solver:
        def __init__(self, N, A, B, H, total):
            self.N = N
            self.B = B
            self.BA = A-B
            self.H = H
            self.len = idiv(total, B)

        def __getitem__(self, k):
            Bk = self.B * k
            cnt = 0
            for i in range(self.N):
                h = H[i] - Bk
                if h < 0:
                    continue
                cnt += idiv(h, self.BA)
                if cnt > k:
                    return -1
            #print("[%d]"%k, cnt, k)
            return 1 if cnt <= k else -1

        def __len__(self):
            return self.len

    k0 = idiv(total, (B*N+A))
    s = Solver(N, A, B, H, total)
    k = bisect(s, 0, k0)
    print(k)

def main():
    input = open(0).readline
    N, A, B = map(int, input().split())
    H = [0]*N
    total = 0
    for i in range(N):
        h = int(input())
        H[i] = h
        total += h
    solve(N, A, B, H, total)

def idiv(x, y):
    if x <= 0:
        return 0
    q, r = divmod(x, y)
    return q + (1 if r > 0 else 0)



main()

Submission status: Accepted

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

def can_defeat(n):
    global mons
    global a
    global b
    base = b*n
    sup = 0
    for m in mons:
        if m-base > 0:
            sup += (m-base)//(a-b)+min((m-base)%(a-b),1)
    if sup <= n:
        return True
    else:
        return False

def bin_search(eval_func,left,right):
    if right-left <= 2:
        for i in range(left,right+1):
            if eval_func(i):
                return i
    mid = (left+right)//2
    if eval_func(mid):
        return bin_search(eval_func,left,mid)
    elif eval_func(right):
        return bin_search(eval_func,mid,right)

print(bin_search(can_defeat,0,int(1e10)))

Submission status: Accepted

Solution code:
def main():

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

    l, r = 0, max(H) // B + 1
    while l < r:
        m = (l + r) // 2
        if isvalid(m, H, N, A, B):
            r = m
        else:
            l = m + 1

    return r

def isvalid(n, H, N, A, B):
    alive = []
    for i in range(len(H)):
        if H[i] - n*B > 0:
            alive.append(H[i]-n*B)
    count = 0
    for v in alive:
        if v % (A-B) == 0:
            count += v //(A-B)
        else:
            count += v //(A-B) + 1
    if count <= n:
        return True
    else:
        return False



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

Submission status: Accepted

Solution code:
import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n,a,b = m()

h = []

for i in range(n):
    h.append(onem())

h.sort(reverse = True)

l = 1
r = h[0]//b+1

while l != r:
    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:
        l = x+1
    else:
        r = x
print(l)

Submission status: Accepted

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

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

    MAX = (h[0] // B) + 1

    l, r = 0, MAX
    while True:
        # print(l, r)
        if l + 1 >= r:
            print(r)
            break
        t = (l + r) // 2
        Bt = B * t
        a = 0
        i = 0
        while i < N and h[i] > Bt:
            tmp = h[i] - Bt
            if tmp % (A-B) == 0:
                a += tmp // (A-B)
            else:
                a += tmp // (A-B) + 1
            i += 1
        # print(t, a)
        if a <= t:# t回で倒しきれる
            l, r = l, t
        else:
            l, r = t, r

if __name__ == "__main__":
    main()

Submission status: Accepted

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

le = 0
ri = max(H) // b + 2
mid = (le + ri) // 2
while ri - le > 1:
    ad_n = 0
    for i in range(n):
        hh = max(0, H[i] - mid * b)
        #print(H[i])
        ad_n += -(-hh // ad)
    #print(ad_n, mid)
    if ad_n > mid:  # 倒せない
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2
print(le+1)

Submission status: Accepted

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

def judge(k):
    _sum = 0
    for hh in h:
        t = hh-k*b
        if t > 0:
            _sum += (t+a-b-1) // (a-b)
            if _sum > k:
                return False;
    return True


high, low = int(1e9+9), 0

while low < high:
    mid = int((high + low) / 2)
    if judge(mid):
        high = mid;
    else:
        low = mid+1;

print(low)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]
l = 0
r = 10 ** 10
c = a - b
while l + 1 != r:
    m = (l + r) // 2
    tmp = 0
    for i in range(n):
        if h[i] > b * m:
            tmp += ((h[i] - b * m) // c + (1 if (h[i] - b * m) % c else 0))
    if tmp > m:
        l = m
    else:
        r = m
print(r)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]
l=1;r=max(h)//b+1
while l!=r:
  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:
    l=x+1
  else:
    r=x
print(l)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc063/tasks/arc075_b
import sys
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop
import math
sys.setrecursionlimit(12345678)


def can_delete(ml, t, a, b):
    for i in range(len(ml)):
        ml[i] -= (b * t)

    count = 0
    for m in ml:
        if m > 0:
            count += math.ceil(m/(a-b))

    return t >= count


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

    l = 0
    r = 10**9
    while l < r:
        m = (l + r) // 2
        if can_delete(monsters[:], m, a, b):
            r = m
        else:
            l = m + 1

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc063/tasks/arc075_b
import sys
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop
import math
sys.setrecursionlimit(12345678)


def can_delete(ml, t, a, b):
    for i in range(len(ml)):
        ml[i] -= (b * t)

    count = 0
    for m in ml:
        if m > 0:
            count += math.ceil(m/(a-b))

    return t >= count


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

    l = 0
    r = 10**9
    while l < r:
        m = (l + r) // 2
        if can_delete(monsters.copy(), m, a, b):
            r = m
        else:
            l = m + 1

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def func(l,r):
    if l == r:
        return l
    c = (l+r)//2
    hoge = 0
    for i in h:
        hoge += max(math.ceil((i-(B*c))/(A-B)),0)
    if hoge > c:
        return func(c+1,r)
    elif hoge < c:
        return func(l,c)
    else:
        return c

print(func(0,10**9+7))

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(t):
    lst = list(map(lambda x: max(0, math.ceil((x-b*t)/(a-b))),h))
    if sum(lst) <= t:
        return True
    return False

n,a,b = LI()
h = [I() for _ in range(n)]
maxh = max(h)
ok,ng = math.ceil(maxh/b),0
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)