Problem:


Score : 400 points

Problem Statement

You are going out for a walk, when you suddenly encounter N monsters. Each monster has a parameter called health, and the health of the i-th monster is h_i at the moment of encounter. A monster will vanish immediately when its health drops to 0 or below.

Fortunately, you are a skilled magician, capable of causing explosions that damage monsters. In one explosion, you can damage monsters as follows:

Select an alive monster, and cause an explosion centered at that monster. The health of the monster at the center of the explosion will decrease by A, and the health of each of the other monsters will decrease by B. Here, A and B are predetermined parameters, and A > B holds.

At least how many explosions do you need to cause in order to vanish all the monsters?

Constraints

All input values are integers.

1 ≤ N ≤ 10^5

1 ≤ B < A ≤ 10^9

1 ≤ h_i ≤ 10^9

Input

Input is given from Standard Input in the following format:

N A B
h_1
h_2
:
h_N

Output

Print the minimum number of explosions that needs to be caused in order to vanish all the monsters.

Sample Input 1

4 5 3
8
7
4
2

Sample Output 1

2

You can vanish all the monsters in two explosion, as follows:

First, cause an explosion centered at the monster with 8 health. The healths of the four monsters become 3, 4, 1 and -1, respectively, and the last monster vanishes.

Second, cause an explosion centered at the monster with 4 health remaining. The healths of the three remaining monsters become 0, -1 and -2, respectively, and all the monsters are now vanished.

Sample Input 2

2 10 4
20
20

Sample Output 2

4

You need to cause two explosions centered at each monster, for a total of four.

Sample Input 3

5 2 1
900000000
900000000
1000000000
1000000000
1000000000

Sample Output 3

800000000



Sample input:
4 5 3
8
7
4
2


Sample output:
2

Submission status: Accepted

Solution code:
import math

def func(h, a, b, count):
  ans = 0
  for v in h:
    if v > b * count:
      ans += math.ceil((v-b*count) / (a-b))
      
  return ans <= count

n,a,b = map(int, input().split())
h = []

for i in range(n):
  # heapqを最大値を取り出すように使いたいのでマイナスにする
  h.append(int(input()))

start = 1
end = math.ceil(max(h) / b)
middle = (end + start) // 2

# 二分探索する、終了条件はぶっちゃけわからん
while True:
  if(func(h,a,b,middle)):
    end = middle
  else:
    start = middle
    
  middle = (end + start) // 2
  if (end - start) <= 1:
    break
    
print(end)

Submission status: Accepted

Solution code:
import math

def func(h, a, b, count):
  ans = 0
  for v in h:
    if v > b * count:
      ans += math.ceil((v-b*count) / (a-b))
      
  return ans <= count

n,a,b = map(int, input().split())
h = []

for i in range(n):
  # heapqを最大値を取り出すように使いたいのでマイナスにする
  h.append(int(input()))

start = 1
end = math.ceil(max(h) / b)
middle = (end + start) // 2

# 二分探索する、終了条件はぶっちゃけわからん
for i in range(1000):
  if(func(h,a,b,middle)):
    end = middle
  else:
    start = middle
    
  middle = (end + start) // 2
  if (end - start) == 1:
    break
    
print(end)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
Hs = [int(input()) for _ in range(N)]
l, r = 0, 10**9+1
while r-l>1:
    half = (l+r)//2
    cum = 0
    for i in range(N):
        h = Hs[i]
        if h<=half*B:
            continue
        cum += -(-(h-half*B)//(A-B))
    if cum>half:
        l = half
    else:
        r = half

print(r)

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 math

def enough(HP,A,B,X):
    q = 0
    for i in range(len(HP)):
        q += max(math.ceil((HP[i] - B * X) / (A - B)),0)
    if q <= X:
        return True
    else:
        return False
    

over = 10 ** 9
under = 0
HP = []
N,A,B = map(int,input().rstrip().split(" "))
for i in range(N):
    HP.append(int(input()))

while abs(over - under) > 1:
    mid = (over + under) // 2
    if enough(HP,A,B,mid):
        over = mid
    else:
        under = mid
print(over)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,A,B = MI()
C = A-B
h = [I() for i in range(N)]

def f(n):  # n回の爆発で討伐完了できるか
    a = 0
    for i in range(N):
        if h[i]-B*n > 0:
            a += (h[i]-B*n+C-1)//C
    if a <= n:
        return True
    else:
        return False

left = 0
right = 10**9
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, A, B, *H = map(int, read().split())
    C = A - B

    ok = 10 ** 9
    ng = 0
    while ok - ng > 1:
        mid = (ok + ng) // 2
        res = 0
        for h in H:
            res += max((h - mid * B + C - 1) // C, 0)
        if res <= mid:
            ok = mid
        else:
            ng = mid

    print(ok)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush
from collections import defaultdict

def main():
    finput=lambda :sys.stdin.readline().strip()
    n,a,b=map(int,finput().split())
    h=[int(finput()) for _ in range(n)]
    gs=lambda a,b:a//b+(a%b>0)
    def enough(t):
        s=sum([max(x-t*b,0)//(a-b)+(max(x-t*b,0)%(a-b)>0) for x in h])
        if s<=t:
            return True
        else:
            return False
    #def biser(t,l):
    #    if l==0:
    #        return t
    #    t=t+l//2
    #    if enough(t):
    #        return biser(t-l//2,l//2)
    #    else:
    #        return biser(t+1,l-l//2)
    l=max(h)//b+1
    t=0
    while l>0:
        t=t+l//2
        if enough(t):
            t=t-l//2
            l=l//2
        else:
            t+=1
            l=l-l//2
    print(t)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush
from collections import defaultdict
import numpy as np

def main():
    finput=lambda :sys.stdin.readline().strip()
    n,a,b=map(int,finput().split())
    h=[int(finput()) for _ in range(n)]
    gs=lambda a,b:a//b+(a%b>0)
    def enough(t):
        s=np.sum([gs(max(x-t*b,0),a-b) for x in h])
        if s<=t:
            return True
        else:
            return False
    #def biser(t,l):
    #    if l==0:
    #        return t
    #    t=t+l//2
    #    if enough(t):
    #        return biser(t-l//2,l//2)
    #    else:
    #        return biser(t+1,l-l//2)
    l=max(h)//b+1
    t=0
    while l>0:
        t=t+l//2
        if enough(t):
            t=t-l//2
            l=l//2
        else:
            t+=1
            l=l-l//2
    print(t)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush
from collections import defaultdict

def main():
    finput=lambda :sys.stdin.readline().strip()
    n,a,b=map(int,finput().split())
    h=[int(finput()) for _ in range(n)]
    gs=lambda a,b:a//b+(a%b>0)
    def enough(t):
        s=sum([gs(max(x-t*b,0),a-b) for x in h])
        if s<=t:
            return True
        else:
            return False
    def biser(t,l):
        if l==0:
            return t
        t=t+l//2
        if enough(t):
            return biser(t-l//2,l//2)
        else:
            return biser(t+1,l-l//2)
    l=max(h)//b+1
    t=biser(0,l)
    #while l>0:
    #    t=t+l//2
    #    if enough(t):
    #        t=t-l//2
    #        l=l//2
    #    else:
    #        t+=1
    #        l=l-l//2
    print(t)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush
from collections import defaultdict


def main():
    finput=lambda :sys.stdin.readline().strip()
    n,a,b=map(int,finput().split())
    h=[int(finput()) for _ in range(n)]
    gs=lambda a,b:a//b+(a%b>0)
    def enough(t):
        s=sum([gs(max(x-t*b,0),a-b) for x in h])
        if s<=t:
            return True
        else:
            return False
    l=max(h)//b+1
    t=0
    while l>0:
        t=t+l//2
        if enough(t):
            t=t-l//2
            l=l//2
        else:
            t+=1
            l=l-l//2
    print(t)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush
from collections import defaultdict
finput=lambda :sys.stdin.readline().strip()

def main():
    n,a,b=map(int,finput().split())
    h=[int(finput()) for _ in range(n)]
    gs=lambda a,b:a//b+(a%b>0)
    def enough(t):
        s=sum([gs(max(x-t*b,0),a-b) for x in h])
        if s<=t:
            return True
        else:
            return False
    l=max(h)//b+1
    t=0
    while l>0:
        t=t+l//2
        if enough(t):
            t=t-l//2
            l=l//2
        else:
            t+=1
            l=l-l//2
    print(t)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil

def f(x,h):
    hp = h
    hp = [hh-(b*x)  for hh in hp]
    count = 0
    for hh in hp:
        if hh <=0: continue
        count += ceil(hh/(a-b))
    return x >= count

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

ng = 0
ok = 10**9
while abs(ok-ng)>1:
    m = (ok+ng)//2
    if f(m,h):
        ok = m
    else:
        ng = m

print(ok)

Submission status: Accepted

Solution code:
import sys,math
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def is_ok(arg):
    chk = 0
    for i in h:
      chk += max(0,math.ceil((-arg*b+i)/(a-b)))
    return chk <= arg


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

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

Submission status: Accepted

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

def f(a):
  E=[]
  for i in range(N):
    if D[i]-a*B>0:
      E.append(D[i]-a*B)
  cnt=0
  for i in E:
    cnt+=-(-i//(A-B))
  if cnt<=a:
    return True
  else:
    return False
l,r=0,10**9
for i in range(50):
  mid=(l+r)//2
  if f(mid):
    r=mid
  else:
    l=mid
print(r)

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
hs = [int(input()) for _ in range(N)]
l=0
r=max(hs)

def enough(x):
  res = 0
  for i in range(N):
    res += max(0,(hs[i]-B*x+A-B-1))//(A-B)
  return res <= x

while l+1 < r:
  m = (l+r)//2
  if enough(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 i in range(N)]

def C(T):
    t = 0
    for i in range(N):
        if h[i] > B*T:
            t += math.ceil((h[i]-B*T)/(A-B))
    if t <= T:
        return True
    else:
        False
l, r = 0, 10**18
while r - l > 1:
    mid = (l+r) // 2
    if C(mid):
        r = mid
    else:
        l = mid


print(r)

Submission status: Accepted

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

from math import ceil
def count(x):
    Hc = deepcopy(H)
    cnt = 0
    for i in range(n):
        Hc[i] -= b*x
        if Hc[i]>0:
            cnt += ceil(Hc[i]/(a-b))
    return cnt <= x

l,r = 0, max(H)//b + 1
while l < r:
    mid = (l+r)//2
    if count(mid):
        r = mid
    else:
        l = mid+1
print(r)

Submission status: Accepted

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

from math import ceil
def count(x):
    Hc = deepcopy(H)
    cnt = 0
    for i in range(n):
        Hc[i] -= b*x
        if Hc[i]>0:
            cnt += (Hc[i]-1)//(a-b) + 1
    return cnt <= x

l,r = 0, max(H)//b + 1
while l < r:
    mid = (l+r)//2
    if count(mid):
        r = mid
    else:
        l = mid+1
print(r)

Submission status: Accepted

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

def enough(t):
    tmp=0
    for i in range(n):
        if h[i]>b*t:
            tmp+=(h[i]-b*t)//(a-b)+(1 if (h[i]-b*t)%(a-b)>0 else 0)
    return True if tmp<=t else False

ok=max(h)
ng=0
mid=(ok-ng)//2
while abs(ok-ng)>1:
    if enough(mid):
        ok=mid
    else:
        ng=mid
    mid=(ok+ng)//2
print(ok)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



# ここから書き始める
def is_ok(key, h, a, b, n):
    total = 0
    for i in range(n):
        if b * key >= h[i]:
            continue
        total += -(-(h[i] - b * key) // (-b + a))
    if total <= key:
        return True
    return False

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

x = -(-max(h) // b)
ng = 0
ok = x + 1

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, h, a, b, n):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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

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

l = 0
r = 10 ** 9 + 1


# x 回で全滅できるか否か
def check(x):
    cnt = 0
    for ri in R:
        if ri - x * b > 0:
            cnt += (ri - x * b + a-b - 1) // (a-b)
    return cnt <= x

while True:
    if r - l <= 1:
        break
    mid = (l + r) // 2
    if check(mid):
        r = mid
    else:
        l = mid

if check(l):
    print(l)
else:
    print(r)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
  n, a, b = map(int, input().split())
  h = [int(input()) for _ in range(n)]
  h.sort()
  
  l, r = -1, h[-1]+1
  while r-l > 1:
    key = (r+l)//2
    count = 0
    for i in range(n):
      if h[i] <= key*b:
        continue
      else:
        count += (h[i]-key*b-1)//(a-b)+1
    if count <= key:
      r = key
    else:
      l = key
  print(r)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N, A, B = MAP()
h = [INT() for _ in range(N)]
h.sort(reverse = True)

def is_OK(T):
	H = h.copy()
	H = [x-B*T for x in h]
	tmp = 0
	for x in H:
		tmp += max(0, -(-x//(A-B)))
		if T < tmp:
			return 0
			break
	else:
		return 1
l = 0
r = -(-max(h)//B)
p = -(-l-r)//2
while l+1 != r:
	p = -(-l-r)//2
	if is_OK(p):
		r = p
	elif is_OK(p)==0:
		l = p

if is_OK(p):
	print(p)
else:
	print(p+1)

Submission status: Accepted

Solution code:
from math import ceil
def isok(x):
    res=0
    for i in range(N):
        H=h[i]-B*x
        if H<=0:
            continue
        res+=ceil(H/(A-B))
    return True if res<=x else False

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

ng,ok=-1,10**10
while(ok-ng>1):
    mid=(ok+ng)//2
    if isok(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
H=[int(input()) for i in range(N)]
L,R,M=0,10**9,0
A-=B
C=0
while L!=R:
  M=(L+R)//2
  C=0
  for i in range(N):
    C+=max(0,(H[i]-B*M+A-1)//A)
  if C>M:
    L=max(M,L+1)
  else:
    R=M
print(L)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, a, b = map(int, readline().split())
    h = [0] * n
    for i in range(n):
        h[i] = int(readline())

    ok = 10 ** 18
    ng = 0

    c = a - b

    while abs(ng - ok) > 1:
        mid = (ng + ok) >> 1
        cnt = 0
        for x in h:
            if x > mid * b:
                cnt += (x - mid * b + c - 1) // c
        if cnt <= mid:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, A, B = map(int, input().split())
h = [0] * N
for i in range(N): h[i] = int(input())
h.sort()

def check(x):
  t = [h[i] - x * B for i in range(N)]
  for i in range(N):
    if t[i] > 0:
      x -= -(-t[i] // (A - B))
      if x < 0: return False
  return x >= 0

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

Submission status: Accepted

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

def hantei(c):
    tmp = 0
    for i in range(n):
        tmp += max(0, -(-(h[i] - b * c) // (a-b)))
    if tmp <= c:
        return True
    else:
        return False

l = 0
r = 10**18+10

while r - l > 1:
    c = (l + r) // 2
    tmp = 0
    for i in range(n):
        tmp += max(0, -(-(h[i] - b * c) // (a-b)))
    if hantei(c):
        r = c
    else:
        l = c

if hantei(l):
    print(l)
else:
    print(r)

Submission status: Accepted

Solution code:
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://qiita.com/drken/items/97e37dd6143e33a64c8c#3-%E3%82%81%E3%81%90%E3%82%8B%E5%BC%8F%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%AE%E3%81%95%E3%82%89%E3%81%AA%E3%82%8B%E5%88%A9%E7%82%B9

    n,a,b=map(int,input().split())
    h=[int(input()) for _ in range(n)]
    def is_ok(t):
        cnt=0
        for i in range(n):
            if h[i]-b*t>0:
                cnt+=math.ceil((h[i]-b*t) / (a-b))
        return cnt<=t

    def bin_search_meguru():
        """
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng, okは,とり得る最小の値-1,とり得る最大の値+1
        """
    
        # 適当にいじる
        ng = 0  # ind=0が条件を満たすこともあるため
        ok = 10**18  # ind=len(a)-1が条件を満たさないこともあるため
    
        # いじらない
        # okとngのどちらが大きいかわからないことを考慮
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    print(bin_search_meguru())
    

    
resolve()

Submission status: Accepted

Solution code:
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://qiita.com/drken/items/97e37dd6143e33a64c8c#3-%E3%82%81%E3%81%90%E3%82%8B%E5%BC%8F%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%AE%E3%81%95%E3%82%89%E3%81%AA%E3%82%8B%E5%88%A9%E7%82%B9

    n,a,b=map(int,input().split())
    h=[int(input()) for _ in range(n)]
    def is_ok(t):
        cnt=0
        for i in h:
            i-=b*t
            if i>0:
                cnt+=math.ceil(i / (a-b))
        return cnt<=t

    def bin_search_meguru():
        """
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng, okは,とり得る最小の値-1,とり得る最大の値+1
        """
    
        # 適当にいじる
        ng = 0  # ind=0が条件を満たすこともあるため
        ok = 10**18  # ind=len(a)-1が条件を満たさないこともあるため
    
        # いじらない
        # okとngのどちらが大きいかわからないことを考慮
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    print(bin_search_meguru())
    

    
resolve()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**9
eps = 10**-7

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

h = [int(readline()) for i in range(N)]

C = A-B
ng = 0 #条件を常に満たさない
ok = INF #条件を常に満たす

def judge(mid):
    ans = 0
    for hi in h:
        ans += max(0,(hi-mid*B+C-1)//C)
    if ans <= mid:
        return True
    return False

while ok - ng > 1:
    mid = (ok + ng) // 2
    if judge(mid):
        ok = mid
    else:
        ng = mid
    #okが答えとなる
print(ok)

Submission status: Accepted

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

#二部探索

ll=0
rr=10**9+1
ab=a-b
while ll<rr:
    half=(ll+rr)//2

    cnt=0
    for hh in h:
        if hh>b*half:
            cnt+=(-1*((-1*(hh-b*half))//ab))
    
    if cnt>half:
        ll=half+1
    elif cnt<half:
        rr=half
    else:
        print(half)
        exit()
print(ll)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    def isOK(mid):
        cnt = 0
        for h in H:
            if h > B * mid:
                sabun = h - B * mid
                cnt += 0 - - sabun // (A - B)
                if cnt > mid:
                    return False
        return True

    ok = 10 ** 9
    ng = 0

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

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def ceil(x,y):
    return -((-x)//y)
#print(ceil(5,2))
n,a,b=MI()
hp=[I() for i in range(n)]
x=0
y=10**9+1
while x+1<y:
    mid=(x+y)//2
    count=0
    for i in range(n):
        count+=max(0,ceil(hp[i]-b*mid,a-b))
    #print(mid,end=" ")
    #print(count<=mid)
    if count<=mid:
        y=mid
    else:
        x=mid
print(y)

Submission status: Accepted

Solution code:
from math import ceil
def solve():
    N, A, B = map(int, input().split())
    H = [int(input()) for _ in range(N)]
    top = max(H)
    total = sum(H)
    bottom = 0
    mid = (top+bottom)//2
    while bottom+1<top:
        cnt = 0
        for i in range(N):
            cnt += max(ceil((H[i]-B*mid)/(A-B)),0)
        if cnt>mid:
            bottom = mid
        else:
            top = mid
        mid = (top+bottom)//2
    ans = top
    return ans
print(solve())

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc063/submissions/5538114
"""

from numpy import ceil,array,sum
import sys

def input():
    return sys.stdin.readline().strip()

def is_ok(m):
    tmp = h - m*B
    tmp[tmp<0] = 0
    
    if ceil(tmp/(A-B)).sum() > m:
        return False
    return True

N,A,B = map(int,input().split())
h = array(list(int(input()) for _ in range(N)))
##二分散策

r = 10**9
l = 0

while abs(l-r) > 1:

    m = (r+l)//2

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

print(r)

Submission status: Accepted

Solution code:
from math import ceil

def is_ok(m):

    tmp = h[:]

    for i in range(N):
        tmp[i] -= m*B

    if not any(tmp):
        return True

    rem = 0
    for i in tmp:
        if i > 0:
            rem += ceil(i/(A-B))

    if rem > m:
        return False

    return True

N,A,B = map(int,input().split())
h = list(int(input()) for _ in range(N))
s = sum(h)
##二分散策

r = 10**10
l = 0

while abs(l-r) > 1:

    m = (r+l)//2

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

print(r)

Submission status: Accepted

Solution code:
from math import ceil

def is_ok(m):

    tmp = h[:]

    for i in range(N):
        tmp[i] -= m*B
    
    flag = True

    for i in tmp:
        if i > 0:
            flag = False
            break

    if flag:##全部0以下
        return True
    else:
        rem = 0
        for i in tmp:
            if i > 0:
                rem += ceil(i/(A-B))

        if rem > m:
            return False

        return True

N,A,B = map(int,input().split())
h = list(int(input()) for _ in range(N))
s = sum(h)
##二分散策

r = 10**10
l = 0

while abs(l-r) > 1:

    m = (r+l)//2

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

print(r)