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 heapq
n,a,b= map(int,input().split())
h =[int(input()) for i in range(n)]
h.sort()
p = a-b
def c(w):
    #w de umakuikkuka
    k = 0
    for i in range(n):
        l[i] = l[i]-b*w
        if l[i] > 0:
            k += l[i]//p
            if l[i] % p != 0:
                k += 1
    if w >= k:
        return True

s = 0
f = 10**14
while f-s >=2:
    m = (f+s)//2
    l = h[::]
    if c(m):
        f = m
    else:
        s = m
l = h[::]
if c(s):
    print(s)
else:
    print(f)

Submission status: Accepted

Solution code:
import heapq
n,a,b= map(int,input().split())
h =[int(input()) for i in range(n)]
h.sort()
p = a-b
def c(w):
    #w de umakuikkuka
    k = 0
    for i in range(n):
        l[i] = l[i]-b*w
        if l[i] > 0:
            k += l[i]//p
            if l[i] % p != 0:
                k += 1
    if w >= k:
        return True

s = 0
f = 10**12
while f-s >=2:
    m = (f+s)//2
    l = h[::]
    if c(m):
        f = m
    else:
        s = m
l = h[::]
if c(s):
    print(s)
else:
    print(f)

Submission status: Accepted

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

p = a-b
def c(w):
    #w de umakuikkuka
    k = 0
    for i in range(n):
        l[i] = l[i]-b*w
        if l[i] > 0:
            k += l[i]//p
            if l[i] % p != 0:
                k += 1
    if w >= k:
        return True

s = 0
f = 10**9
while f-s >=2:
    m = (f+s)//2
    l = h[::]
    if c(m):
        f = m
    else:
        s = m
l = h[::]
if c(s):
    print(s)
else:
    print(f)

Submission status: Accepted

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

from math import ceil

t = sum(H)

def enough(t):
    r = 0
    for h in H:
        r += ceil(max(h - t * B, 0) / (A - B))
    # print("*", t, r)
    return r <= t

lo = ceil(t / (A + B * (N - 1))) - 1
hi = ceil(t / B)

while lo + 1 != hi:
    t = (lo + hi) // 2
    r = enough(t)
    # print(lo, hi, t, r)
    if r:
        hi = t
    else:
        lo = t

print(hi)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n, a, b = f.read_int_list()
    h = [f.read_int() for _ in xrange(n)]

    def check(num):
        s = 0
        for hi in h:
            s += max(0, (hi-num*b+(a-b-1))/(a-b))
        return s <= num

    ma = 10**10
    mi = 0

    while ma - mi > 1:
        mid = (ma+mi)/2
        if check(mid):
            ma = mid
        else:
            mi = mid

    return ma


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

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

    ms.sort()

    times = [0 for i in range(n)]
    for i in range(n):
        times[i] = (ms[i]+b-1) // b

    left, right = -1, max(times)
    while right - left > 1:
        mid = (left+right) // 2
        center = 0
        for i in range(n):
            if ms[i] - mid * b > 0:
                exd = a - b
                center += (ms[i]-mid*b+exd-1) // exd

        if center - mid > 0:
            left = mid
        else:
            right = mid

    print(right)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

N, A, B = map(int, input().split())
C = A - B

E = np.array([int(input()) for _ in range(N)], dtype=np.int64)
Z = np.zeros(N, dtype=np.int64)

OK = (np.max(E) // B) + 1
NG = 0

while (OK - NG) > 1:
    m = (OK + NG)//2

    if -np.sum((-np.maximum(Z, E-m*B) // C)) <= m:
        OK = m
    else:
        NG = m

print(OK)

Submission status: Accepted

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

sup = 10**9
inf = 0
add = A-B


def binary(check):
    count = check
    for i in range(N):
        ch = h[i] - B*check
        if ch <= 0:
            continue
        else:
            count -= math.ceil(ch/add)
        if count < 0:
            break
    if count < 0:
        return False
    else:
        return True


while sup > inf+1:
    p = (sup+inf)//2
    if binary(p):
        sup = p
    else:
        inf = p
print(sup)

Submission status: Accepted

Solution code:
import math

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

high = 10 ** 9
low = 0


def enough(mid):
    aoe = b * mid
    count = 0
    for hp in h:
        remain = hp - aoe
        if remain > 0:
            count += math.ceil(remain / critical)
    return count <= mid


while high - low > 1:
    mid = (low + high) // 2
    if enough(mid):
        high = mid
    else:
        low = mid
print(high)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# from numpy import array, sum

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

h_li = []

for i in range(N):
	h_li.append(int(input()))

def all_beatable_check(k):
	# All enemy get B damage every time
	h_damaged = [h - B*k for h in h_li]
	# print(h_damaged)
	# A-B damage will be additionally given to enemies s.t. HP > 0
	ex_dmg = A - B
	h_ex_needed = [(h+ex_dmg-1) // ex_dmg if h > 0 else 0 for h in h_damaged]
	# print(h_ex_needed)
	# how many A-B damage is needed to beat all enemies
	hits_needed = sum(h_ex_needed)
	if hits_needed > k:
		return False
	else:
		return True

MIN_K = 0         # impossible
MAX_K = max(h_li) # possible

while MAX_K - MIN_K > 1:
	# print(f"{MIN_K}-{MAX_K} {MIN_K + (MAX_K - MIN_K) // 2}")
	k = (MIN_K + MAX_K) // 2
	res = all_beatable_check(k)
	if res is True:
		MAX_K = k
	elif res is False:
		MIN_K = k

print(MAX_K)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# from numpy import array, sum

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

h_li = []

for i in range(N):
	h_li.append(int(input()))

def all_beatable_check(k):
	# All enemy get B damage every time
	h_damaged = [h - B*k for h in h_li]
	# print(h_damaged)
	# A-B damage will be additionally given to enemies s.t. HP > 0
	ex_dmg = A - B
	h_ex_needed = [(h+ex_dmg-1) // ex_dmg if h > 0 else 0 for h in h_damaged]
	# print(h_ex_needed)
	# how many A-B damage is needed to beat all enemies
	hits_needed = sum(h_ex_needed)
	if hits_needed > k:
		return False
	else:
		return True

MIN_K = 0         # impossible
MAX_K = max(h_li) # possible

while MAX_K - MIN_K > 1:
	# print(f"{MIN_K}-{MAX_K} {MIN_K + (MAX_K - MIN_K) // 2}")
	k = MIN_K + (MAX_K - MIN_K) // 2
	res = all_beatable_check(k)
	if res is True:
		MAX_K = k
	elif res is False:
		MIN_K = k

print(MAX_K)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# from numpy import array, sum

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

h_li = []

for i in range(N):
	h_li.append(int(input()))

def all_beatable_check(k):
	# All enemy get B damage every time
	h_damaged = [h - B*k for h in h_li]
	# print(h_damaged)
	# A-B damage will be additionally given to enemies s.t. HP > 0
	ex_dmg = A - B
	h_ex_needed = [(h+ex_dmg-1) // ex_dmg if h > 0 else 0 for h in h_damaged]
	# print(h_ex_needed)
	# how many A-B damage is needed to beat all enemies
	hits_needed = sum(h_ex_needed)
	if hits_needed > k:
		return False
	else:
		return True

MIN_K = 1
MAX_K = max(h_li)

while True:
	if MIN_K == MAX_K:
		print(MIN_K)
		break
	# print(f"{MIN_K}-{MAX_K} {MIN_K + (MAX_K - MIN_K) // 2}")
	k = MIN_K + (MAX_K - MIN_K) // 2
	res = all_beatable_check(k)
	if res is True:
		MAX_K = k
	elif res is False:
		MIN_K = k + 1

Submission status: Accepted

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

def check(cnt):
	h = [0] * n
	for i in range(n):
		if pre_h[i] - b * cnt > 0:
			h[i] = pre_h[i] - b * cnt
		else:
			h[i] = 0

	if sum([(i - 1) // (a - b) + 1 for i in h]) <= cnt:
		return True
	else:
		return False

minimum = 1
maximum = (max(pre_h) - 1) // b + 1

while maximum - minimum > 1:
	if check(minimum + (maximum - minimum) // 2):
		maximum = minimum + (maximum - minimum) // 2
	else:
		minimum = minimum + (maximum - minimum) // 2

print(maximum)

Submission status: Accepted

Solution code:
def ok(a, b, hs, s):
    count = 0
    for h in hs:
        num, den = h-b*s, a-b
        if num < 0:
            continue
        count += (num+den-1)//den
    return count <= s

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

lo, hi = 0, 10**18
while(lo < hi):
    mi = (lo+hi)//2
    if(ok(a, b, hs, mi)):
        hi = mi
    else:
        lo = mi+1

print(lo)

Submission status: Accepted

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

def enough(n):
    bomb = 0
    for h in src:
        if h <= B*n: continue
        h -= B*n
        bomb += (h-1)//(A-B) + 1
        if bomb > n: return False
    return True

#ok/ng: 中点が十分に大きいかどうか
ng = 0
ok = 10**9
while ok - ng > 1:
    m = (ok+ng) // 2
    if enough(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Accepted

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

def enough(n):
    used = 0
    for h in src:
        if h <= B*n: continue
        h -= B*n
        used += (h-1)//(A-B) + 1
        if used > n: return False
    return True

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

Submission status: Accepted

Solution code:
from math import ceil
import numpy as np
n, a, b = map(int, input().split())
h = np.array(sorted([int(input()) for i in range(n)]))

def enough(T):
    global h
    h2 = h - b * T
    c = sum(np.ceil(h2[h2 > 0]/(a - b)))
    if c <= T: return 1
    else: return 0

def bisearch():
    lo = 0
    hi = ceil(max(h)/b)
    while lo < hi:
        mid = (lo + hi) // 2
        midval = enough(mid)
        if midval < 1: lo = mid + 1
        else: hi = mid
    return lo

print(bisearch())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

H = sorted(H)
l = sum(H) // (A+B*(N-1))
r = sum([h//A + (h%A>0) for h in H])

def judge(m):
    nH = [h - B*m for h in H]
    if sum([h//D + (h%D>0) for h in nH if h > 0]) <= m:
        return True
    else:
        return False

while r-l > 1:
    mid = (l+r)//2
    if judge(mid):
        r = mid
    else:
        l = mid
if judge(l):
    print(l)
else:
    print(r)

Submission status: Accepted

Solution code:
def good(x):
	VC = list(V)

	Breduce = B * x

	for i in range(N):
		VC[i] -= Breduce

	required = 0

	for i in range(N):
		if VC[i] > 0:
			required += (VC[i] + A - 1) / A

	if required <= x:
		return True
	else:
		return False

N, A, B = map(int, raw_input().split(' '))
A = A - B

V = [0 for i in range(N)]

for i in range(N):
	V[i] = int(raw_input())

l = 1
r = 1000000000000000000
best = 1000000000000000000


while l <= r:
	mid = (l + r) / 2
	if good(mid):
		r = mid - 1
		best = mid
	else:
		l = mid + 1

print best

Submission status: Accepted

Solution code:
def widespread_2():
	n, a, b = map(int, raw_input().split(" "))
	monsters = []
	for i in range(n):
		monsters.append(int(raw_input()))
	# as a>b holds
	dif_a_b = a - b
	max_ans = int(max(monsters)/b)+1
	min_ans = int(max(monsters)/a)-1
	# using binary search
	while min_ans+1 < max_ans:
		current_attepmt = (max_ans+min_ans)/2
		# print current_attepmt
		re = _inner_widespread_2(monsters, current_attepmt, a, b)
		# print re
		if re>current_attepmt:
			min_ans = current_attepmt
		else:
			max_ans = current_attepmt
	print max_ans


def _inner_widespread_2(monsters, attemps, a, b):
	dif = a-b
	re = 0
	for e in monsters:
		update_e = e-b*attemps
		if update_e>0:
			if update_e%dif==0:
				re = re+update_e/dif
			else:
				re = re + int(update_e/dif)+1
	return re


if __name__ == "__main__":
	widespread_2()

Submission status: Accepted

Solution code:
from math import ceil

n, a, b = map(int, input().rstrip("\n").split(" "))

h = []
total = 0
for i in range(n):
  value = int(input()) 
  h.append(value)
def solve(a, b):
  diff = a - b
  total = sum(h)

  h.sort()

  right = ceil(total // b)  + len(h)
  center = right // 2
  left = 0

  def check(b_count, h):
     b_total = b * b_count
     #print("b_total",b_total)
     #print("diff",diff)
     count = 0
     for value in h:
       remain = value - b_total
       #print("remain",remain)
       if remain > 0:
         count += ceil( remain  /  diff)
     return count - b_count

  result = 0
  while left < right:

     center = (left + right) // 2
     result = check(center, h)
     #print(left,right, result)
     if result < 0:
       right = center 
     elif result > 0:
       left= center + 1
     if result == 0:
       break
  center = (left + right) // 2
  #print(left,center,right)
  return center

print(solve(a, b))
#for b in range(1,a):
#  print(a, b ,"=", solve(a, b))

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
extra_damage = a - b
h = [int(input()) for i in range(n)]
# h.sort()
INF = sum(h)
l = 0
r = INF


def widespread(bomb):
    base = b * bomb
    for hi in h:
        if hi - base > 0:
            bomb -= (hi - base + extra_damage - 1) // extra_damage
    return bomb >= 0

while l+1 < r:
    m = (l+r)//2
    if widespread(m):
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

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

def judge(n):
    H = [h - n*B for h in h_list]
    H_2 = [int((h-1)/(A-B)) + 1 if h > 0 else 0 for h in H]
    return sum(H_2) <= n

M = int(h_max / B) + 1
m = 0

while M-m > 1:
    n = int((M+m)/2)
    if judge(n):
        M = n
    else:
        m = n

print(M)

Submission status: Accepted

Solution code:
import bisect
from math import ceil


def can_exterminate(attack_count):
    sum_b = b * attack_count
    i = bisect.bisect(enemies, sum_b)

    for enemy in enemies[i:]:
        attack_count -= ceil((enemy - sum_b) / d)
        if attack_count < 0:
            return False
    return True


def binary_search(max_attack_count):
    l, r, m = 1, max_attack_count + 1, 0
    while l < r:
        m = (l + r) // 2
        if can_exterminate(m):
            r = m
        else:
            l = m + 1
    return l


n, a, b = map(int, input().split())
d = a - b
enemies = sorted(int(input()) for _ in range(n))
boss = max(enemies)
print(binary_search(ceil(boss / b)))

Submission status: Accepted

Solution code:
from math import ceil


def enough(x):
    total = 0
    for hi in h:
        total += max(0, ceil((hi - B * x) / (A - B)))
        if total > x:
            return False
    return True

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

l, r = (h[0] // A), (h[-1] // B + 1)
while l + 1 < r:
    m = (l + r) // 2
    if enough(m):
        r = m
    else:
        l = m

print(l if enough(l) else r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
import sys
from io import StringIO

def read():
    return int(input())

def reads():
    return [int(x) for x in input().split()]

setrecursionlimit(1000000)

# inputstr = """
# 2 10 4
# 20
# 20
# """[1:]
# sys.stdin = StringIO(inputstr)

(N, A, B) = reads()
H = [0] * N

for i in range(N):
    H[i] = read()

def satisfy(t):
    q = A - B
    cnt = sum((max(h-B*t, 0) + q - 1)//q for h in H)
    return cnt <= t

(l, r) = (0, 10**9)

while True:
    if l + 1 == r:
        break
    m = (l + r) // 2
    if satisfy(m):
        r = m
    else:
        l = m

print(r)

Submission status: Accepted

Solution code:
def min_bs(l,r):
    l-=1
    while r-l>1:
        m=(r+l)/2
        if check(m):
            r=m
        else:
            l=m
    return r

def check(m):
    cnt=0
    for i in xrange(n):
        if h[i]-b*m<=0:continue
        cnt+=(h[i]-b*m-1)/(a-b)+1
    return True if m>=cnt else False

n,a,b=map(int,raw_input().split())
h=[int(raw_input()) for _ in xrange(n)]
print min_bs(1,10**9)

Submission status: Accepted

Solution code:
import math
N,A,B = map(int,input().split())
H = [int(input()) for i in range(N)]
Hs = sum(H)
c = A - B
M = math.ceil(max(H) / B)

m = max(H) // A

while M - m > 1:
	n = (M + m) // 2
	H2 = [math.ceil((H[i] - n * B) / c) for i in range(N) if H[i] - n * B > 0]
	cnt = sum(H2)
	if cnt > n:
		m = n
	elif cnt == n:
		M = n
		break
	else:
		M = n
print(M)

Submission status: Accepted

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

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

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 bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,a,b = LI()
    ab = a - b
    h = sorted([I() for _ in range(n)], reverse=True)
    def ff(t):
        bt = b*t
        c = 0
        for w in h:
            if w <= bt:
                return False
            c += (w - bt + ab - 1) // ab
            if c > t:
                return True
        return False

    return bs(ff, 0, sum(h) // b + 1)



print(main())

Submission status: Accepted

Solution code:
import sys

import math


class Solution(object):
    def __init__(self):
        self.N, self.A, self.B = map(int, sys.stdin.readline().split(' '))
        self.h = []
        for _ in range(self.N):
            self.h.append(int(sys.stdin.readline()))
        self.extra_damage = self.A - self.B

    def solve(self):
        max_h = max(self.h)
        at_most = int(max_h / self.B) + 1
        at_least = int(max_h / self.A) + 1
        result = self.binary_search_lowest_kaisu(at_least, at_most)
        print(result)

    def binary_search_lowest_kaisu(self, low, high):
        if low == high:
            return low
        mid = low + (high - low) // 2
        if self.enough(mid):
            return self.binary_search_lowest_kaisu(low, mid)
        else:
            return self.binary_search_lowest_kaisu(mid + 1, high)

    def enough(self, kaisu):
        hps_remain = []
        for x in self.h:
            hp_remain = x - kaisu * self.B
            if hp_remain > 0:
                hps_remain.append(hp_remain)
        counter = 0
        for hp_remain in hps_remain:
            counter += math.ceil(hp_remain / self.extra_damage)
            if counter > kaisu:
                return False
        return True

Solution().solve()

Submission status: Accepted

Solution code:
from sys import stdin 
n,x,y = map(int,stdin.readline().split())
a = []
for _ in xrange(n):
    a.append(int(stdin.readline()))
lo = 0
hi = 10**18 
def solve(tim):
    tot = 0 
    for i in a:
        if i > tim * y:
            rem = i - tim * y 
            tot += rem / (x-y) 
            if rem % (x-y) :
                tot += 1 
    return tot <= tim 
while hi > lo + 1 :
    mid = (lo + hi )/2 
    if solve(mid):
        hi = mid 
    else:
        lo = mid 
for ans in xrange(lo,hi+1):
    if solve(ans):
        break 
print ans

Submission status: Accepted

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

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

nmax = 10 ** 10
nmin = 0
while nmax - nmin > 1:
    n = (nmax + nmin) / 2
    if check(H, A, B, n):
        nmax = n
    else:
        nmin = n
print nmax

Submission status: Accepted

Solution code:
n, a, b = [int(i) for i in input().split()]
hs = [None]*n
kill_b = [None]*n
for i in range(n):
    hs[i] = int(input())
max_hp = max(hs)
ret = 0
ab = a - b
right = max_hp // b
if((max_hp % b) != 0):
    right += 1
left = 1
while right != left:
    middle = (right + left) // 2
    # print([left, right, middle])
    all_a = 0
    for x in hs:
        nokori = x - (b * middle)
        if(nokori > 0):
            num_a = nokori // ab
            if(x > num_a * a + (middle - num_a) * b):
                num_a += 1
            all_a += num_a
    if(all_a <= middle):
        right = middle
    else:
        left = middle + 1
ret = right
print(ret)

Submission status: Accepted

Solution code:
#coding:utf-8

import math

def enough(A, B, h_list, T):
    h_list = filter(lambda x: (x - B * T) > 0, h_list)
    h_list = map(lambda x : x - B * T, h_list)

    exp_num = 0
    for val in h_list:
        exp_num += math.ceil(val / (A - B))

    if exp_num <= T:
        return True
    else:
        return False

def binary_search(A, B, h_list, T_min, T_max):
    if T_min == T_max:
        return T_min
    else:
        T_mid = T_min + (T_max - T_min) // 2
        if enough(A, B, h_list, T_mid):
            return binary_search(A, B, h_list, T_min, T_mid)
        else:
            return binary_search(A, B, h_list, T_mid + 1, T_max)

if __name__ == "__main__":
    N, A, B = map(int, input().split(" "))

    h_list = []
    for i in range(N):
        h_list.append(int(input()))

    T_max = math.ceil(sum(h_list) / B)
    print(binary_search(A, B, h_list, 0, T_max))

Submission status: Accepted

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

H = [int(input()) for i in range(N)]

d = A-B

temp = max(H)
low = temp//A - 1
high = temp//B+1

while low + 1 < high:
  mid = (low+high)//2
  offset = mid*B
  cnt = -sum((offset-h)//d for h in H if h > offset)
  if cnt > mid:
    low = mid
  else:
    high = mid

print(high)

Submission status: Accepted

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

H = [int(input()) for i in range(N)]

low = sum(H)//(len(H)*B+A-B) - 1
high = max(H)//B+1

d = A-B
ceildiv = lambda x,y: -(-x//y)

while low + 1 < high:
  mid = (low+high)//2
  offset = mid*B
  cnt = sum(max(ceildiv(h - offset, d),0) for h in H)
  if cnt > mid:
    low = mid
  else:
    high = mid

print(high)

Submission status: Accepted

Solution code:
import math

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

m = sum(hs) // (a + (n-1)*b) - 1
#M = sum(math.ceil(h/a) for h in hs)
M = max(hs) // b + 1

def killable(p, hs, a, b):
    x = sum(max(0, math.ceil((h-p*b) / (a-b))) for h in hs)
    return x <= p

while(m+1 < M):
    c = (m+M) // 2
    if killable(c, hs, a, b):
        M = c
    else:
        m = c
print(M)

Submission status: Accepted

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

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

def f(n):
    needed_attacks = 0
    for h in H:
        r = h - B * n
        if r < 0:
            r = 0

        if r % D == 0:
            needed_attacks += r // D
        else:
            needed_attacks += r // D + 1

    return needed_attacks <= n

s = 0
e = max(H) // B + 1

while e - s > 1:
    m = (s + e) // 2
    if f(m):
        e = m
    else:
        s = m

print(e)

Submission status: Accepted

Solution code:
import math

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

m = sum(hs) // (a + (n-1)*b) - 10
M = sum(math.ceil(h/a) for h in hs)

def killable(p, hs, a, b):
    x = sum(max(0, math.ceil((h-p*b) / (a-b))) for h in hs)
    return x <= p

while(m+1 < M):
    c = (m+M) // 2
    if killable(c, hs, a, b):
        M = c
    else:
        m = c
print(M)

Submission status: Accepted

Solution code:
import math

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

h = []
min_h = 10 ** 10
max_h = 0
for _ in range(N):
    hi = int(input())
    if hi < min_h:
        min_h = hi
    if hi > max_h:
        max_h = hi
    h.append(hi)
    
min_K = math.ceil(min_h / A)
max_K = math.ceil(max_h / B)
K = min_K
while(min_K != max_K):
    sum_x = 0
    for i, n in enumerate(h):
        x = math.ceil((n - K * B) / (A - B))
        if x > 0:
            sum_x += x
    #x = [math.ceil((n - K * B) / (A - B)) for n in h]
    #sum_x = sum([xi for xi in x if xi > 0])
    if sum_x <= K:
        max_K = K
        K = math.floor((min_K + K) / 2)
    else:
        min_K = K + 1
        K = math.floor((K + max_K) / 2) + 1

print(K)

Submission status: Accepted

Solution code:
import math

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

h = []
min_h = 10 ** 10
max_h = 0
for _ in range(N):
    hi = int(input())
    if hi < min_h:
        min_h = hi
    if hi > max_h:
        max_h = hi
    h.append(hi)
    
min_K = math.ceil(sum(h) / (A - B + B * N)) - 1
max_K = math.ceil(max(h) / A) * N
min_K = math.ceil(min_h / A)
max_K = math.ceil(max_h / B)
K = min_K
while(min_K != max_K):
    x = [math.ceil((n - K * B) / (A - B)) for n in h]
    sum_x = sum([xi for xi in x if xi > 0])
    if sum_x <= K:
        max_K = K
        K = math.floor((min_K + K) / 2)
    else:
        min_K = K + 1
        K = math.floor((K + max_K) / 2) + 1

print(K)

Submission status: Accepted

Solution code:
import math

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

h = []
min_h = 10 ** 10
max_h = 0
for _ in range(N):
    hi = int(input())
    if hi < min_h:
        min_h = hi
    if hi > max_h:
        max_h = hi
    h.append(hi)
    
min_K = math.ceil(min_h / A)
max_K = math.ceil(max_h / B)
K = min_K
while(min_K != max_K):
    x = [math.ceil((n - K * B) / (A - B)) for n in h]
    sum_x = sum([xi for xi in x if xi > 0])
    if sum_x <= K:
        max_K = K
        K = math.floor((min_K + K) / 2)
    else:
        min_K = K + 1
        K = math.floor((K + max_K) / 2) + 1

print(min_K)

Submission status: Accepted

Solution code:
import math

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

h = []
min_h = 10 ** 10
max_h = 0
for _ in range(N):
    hi = int(input())
    if hi < min_h:
        min_h = hi
    if hi > max_h:
        max_h = hi
    h.append(hi)
    
min_K = math.ceil(min_h / A)
max_K = math.ceil(max_h / B)
K = min_K
while(min_K != max_K):
    x = [math.ceil((n - K * B) / (A - B)) for n in h]
    sum_x = sum([xi for xi in x if xi > 0])
    if sum_x <= K:
        max_K = K
        K = int((min_K + K) / 2)
    else:
        min_K = K + 1
        K = int((K + max_K) / 2) + 1

print(min_K)

Submission status: Accepted

Solution code:
import math as mt
n,a,b = map(int,input().split())
h = []
for i in range(n):
    h.append(int(input()))
left = mt.ceil(min(h)/a)
right = mt.ceil(max(h)/b)
while left <= right :
    K = mt.floor((left + right) / 2)
    if(left == right):
        print(K)
        break
    else:
        sum = 0
        for i in range(n):
            sum += max(0, mt.ceil((h[i] - K*b)/(a-b)))
        if(sum <= K):
            right = K
        else:
            left = K+1

Submission status: Accepted

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

def can_clear(n):
    res = 0
    for i in range(N):
        res += max(0, math.ceil((H[i] - B*n) / (A - B)))
    if res > n:
        return False
    else:
        return True


# search
# 0:False
# NR:True
NR = math.ceil(max(H) / B)
NL = 0
while True:
    NM = math.ceil((NR + NL) / 2)
    if NM == NR:
        break
    if can_clear(NM):
        NR = NM
    else:
        NL = NM
print(NM)

Submission status: Accepted

Solution code:
import math


def rren(): return list(map(int, input().split()))


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


left = 0
right = math.ceil(max(h)/B)
while(left <= right):
    K = math.floor((left + right) / 2)
    if(left == right):
        print(K)
        break
    else:
        sum = 0
        for i in range(N):
            sum += max(0, math.ceil((h[i] - K*B)/(A-B)))
        if(sum <= K):
            right = K
        else:
            left = K+1