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 as mt
store = []
def binarysearch(min, max):
    mid = int((max + min)/2)
    if (min == max):
        return mid
    elif count(mid) > mid:
        return binarysearch(mid+1, max)
    else:
        return binarysearch(min, mid)

def count(x):
    store = [mt.ceil((n - x*b)/a) for n in hp]
    store = [x for x in store if x > 0]
    return sum(store)

st = 0
min = 10 ** 18
max = 0
n, a, b = [int(x) for x in input().split(' ')]
hp = []
for i in range(n):
    st = int(input())
    if st < min:
        min = st
    if st > max:
        max = st
    hp.append(st)
min, max = mt.ceil(min/a), mt.ceil(max/b)
a = a - b
print(binarysearch(min,max))

Submission status: Accepted

Solution code:
import sys

def solve():
    n, a, b = map(int, sys.stdin.readline().split())
    h = [int(sys.stdin.readline().rstrip()) for i in range(n)]

    top = n * (max(h) + a - 1) // a
    btm = 0

    while top - btm > 1:
        mid = (top + btm) // 2

        if check(n, a, b, h, mid):
            top = mid
        else:
            btm = mid

    print(top)

def check(n, a, b, h, k):
    base = k * b
    dif = a - b
    cnt = 0

    for hi in h:
        if hi > base:
            cnt += (hi - base + dif - 1) // dif

            if cnt > k:
                return False

    return True

if __name__ == '__main__':
    solve()

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(Hs / B)

m = 0

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

Submission status: Accepted

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

l = 0
r = 1000000000
while 1 < r - l:
    c = (l + r) // 2
    if c < sum(list(map(lambda hi: max((hi - b * c + d - 1) // d, 0), h))):
        l = c
    else:
        r = c

print(r)

Submission status: Accepted

Solution code:
n, a, b = [int(_) for _ in raw_input().split()]
h = [int(raw_input()) for _ in xrange(n)]

d = a - b


def c(n):
    m = 0
    for hi in h:
        m += max(0, -((b * n - hi) // d))
    return m <= n


lb = 0
ub = -(-max(h) // b) + 1
while lb < ub:
    mid = (lb + ub) // 2
    if c(mid):
        ub = mid
    else:
        lb = mid + 1

print lb

Submission status: Accepted

Solution code:
n,a,b=map(int,raw_input().split())
h=[int(raw_input()) for _ in xrange(n)]
l=0
r=10**12
while r-l>1:
    m=(r+l)/2
    c=a-b
    cnt=0
    for i in xrange(n):
        if h[i]-b*m<0:continue
        if (h[i]-b*m)%c==0:
            cnt+=(h[i]-b*m)/c
        else:
            cnt+=(h[i]-b*m)/c+1
    if cnt<=m:
        r=m
    else:
        l=m
print r

Submission status: Accepted

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

l = 0
r = 1000000000
while 1 < r - l:
    c = (l + r) // 2
    if c < sum(list(map(lambda hi: (hi - b * c + d - 1) // d if 0 < hi - b * c else 0, h))):
        l = c
    else:
        r = c

print(r)

Submission status: Accepted

Solution code:
from math import ceil

def check(N, hps, A, B):
    n = N
    C = A - B
    for rem_hp in map(lambda x: x - B * N, hps):
        if rem_hp < 0:
            continue
        n -= ceil(rem_hp / C)
        if n < 0:
            return False
    return True

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

if __name__ == "__main__":
    # print(check(1, [8, 7, 4, 2], 5, 3))
    # print(check(3, [8, 7, 4, 2], 5, 3))
    # print(check(2, [8, 7, 4, 2], 5, 3))
    main()

Submission status: Accepted

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

left = 0; right = 10**9+1
while left+1 < right:
    mid = (left + right) / 2
    cnt = 0
    for h in H:
        h -= mid * b
        if h > 0:
            cnt += (h + a-b - 1) / (a-b)
    if mid < cnt:
        left = mid
    else:
        right = mid
print right

Submission status: Runtime Error

Solution code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

// using System.Numerics;
using System.Runtime.CompilerServices;
using System.Diagnostics;
using ll=System.Int64;
using static Contest_D.MyIO;



public class Contest_D
{
	static void swap1<T>(ref T a, ref T b) { T t = a; a = b; b = t; }
	static void swap2<T>(ref T a, ref T b) where T : IComparable { if (a.CompareTo(b)==1) swap1(ref a, ref b); }  // b の方が小さければ交換
	static bool chmin<T>(ref T a, T b) where T : IComparable { if (a.CompareTo(b)== 1) { a = b; return true; } return false; }  // b の方が小さければ a を更新
	static bool chmax<T>(ref T a, T b) where T : IComparable { if (a.CompareTo(b)==-1) { a = b; return true; } return false; }  // b の方が大きければ a を更新
	static bool inside(long i, long n) => (0<=i&&i<n);
	static bool inside(long x, long y, long w, long h) => (inside(x,w)&&inside(y,h));
	static T min<T>(params T[] a) where T : IComparable => a.Min();
	static T max<T>(params T[] a) where T : IComparable => a.Max();
	static long mod(long a, long m) { var v = a%m; return (v<0?v+m:v); }
	static T[][] init<T>(long len1,long len2,T val) where T : struct { T[][] m = new T[len1][]; for (int i=0;i<m.Length;i++) m[i] = Enumerable.Repeat(val,(int)len2).ToArray(); return m; }
	static T[][][] init<T>(long len1,long len2,long len3,T val) where T : struct { T[][][] m = new T[len1][][]; for (int i=0;i<m.Length;i++) m[i] = init(len2,len3,val); return m; }
	public const long MOD1 = 1000000007; // 10^9+7
	public const double EPS1 = 1e-8;
	public const long INF1 = 1000000000000000;  // 10^15

	public static void Main() {
		checked{
			long  n, a, b;
			MyIO.RM(out n, out a, out b);
			ll[] h;
			RL(n, out h);

			Array.Sort(h);
			Func<ll,ll> f=(k)=>{
				ll bs = k*b;
				ll r = 1;
				foreach (var e in h)
				{
					ll q = e-bs;
					k -= q/(a-b)+(q%(a-b)==0?0:1);
					if(k<0){ 
						r=0;
						break;
					}
				}
				return r;
			};

			ll ans = BS(f,1);






			MyIO.WM(ans);
		}
	}
    public static long BS<T>(Func<long,T> seq, T value)  where T : IComparable<T> {
        long left = long.MinValue/4;
        long right = long.MaxValue/4;
        while (right - left > 1) {
            long mid = left + (right - left) / 2;
            if (0<=seq(mid).CompareTo(value)) right = mid;
            else left = mid;
        }
        return right;
    }
public class PriorityQueue<T>
{
    private readonly List<T> heap;
    private readonly Comparison<T> compare;
    private int size;
    public PriorityQueue() : this(Comparer<T>.Default) {} 
    public PriorityQueue(IComparer<T> comparer) : this(16, comparer.Compare) { }
    public PriorityQueue(Comparison<T> comparison) : this(16, comparison) { }
    public PriorityQueue(long capacity, Comparison<T> comparison)
    {
        this.heap = new List<T>((int)capacity);
        this.compare = comparison;
    }
    public void Enqueue(T item)
    {
        this.heap.Add(item);
        var i = size++;
        while (i > 0)
        {
            var p = (i - 1) >> 1;
            if (compare(this.heap[p], item) <= 0)
                break;
            this.heap[i] = heap[p];
            i = p;
        }
        this.heap[i] = item;

    }
    public T Dequeue()
    {
        var ret = this.heap[0];
        var x = this.heap[--size];
        var i = 0;
        while ((i << 1) + 1 < size)
        {
            var a = (i << 1) + 1;
            var b = (i << 1) + 2;
            if (b < size && compare(heap[b], heap[a]) < 0) a = b;
            if (compare(heap[a], x) >= 0)
                break;
            heap[i] = heap[a];
            i = a;
        }
        heap[i] = x;
        heap.RemoveAt(size);
        return ret;
    }
    public T Peek() { return heap[0]; }
    public long Count { get { return size; } }
    public bool Any() { return size > 0; }
}











#region MyIO

public struct VT<T,U>
{
	public T Item1; public U Item2;
    public VT(T a,U b) { Item1 = a; Item2 = b; }
}
public struct VT<T,U,V>
{
	public T Item1; public U Item2; public V Item3;
    public VT(T a,U b,V c) { Item1 = a; Item2 = b; Item3 = c; }
}
public struct VT<T,U,V,W>
{
	public T Item1; public U Item2; public V Item3; public W Item4;
    public VT(T a,U b,V c,W d) { Item1 = a; Item2 = b; Item3 = c; Item4 = d; }
}

public static class MyIO
{
	class Prt : System.IO.StreamWriter
	{
		public override IFormatProvider FormatProvider { get { return System.Globalization.CultureInfo.InvariantCulture; } }
		public Prt(System.IO.Stream s) : base(s,new UTF8Encoding(false,true)) {}
		public Prt(System.IO.Stream s,Encoding e) : base(s,e) {}
	}
	
	static char[] sp = new char[] {' '};
	[MethodImpl(256)]
	static bool eq<T,U>() => typeof(T).Equals(typeof(U));
	[MethodImpl(256)]
	static T ct<T,U>(U a) => (T)Convert.ChangeType(a,typeof(T));
	static T cv<T>(string s) =>
		eq<T,int>()    ? ct<T,int>(int.Parse(s))
	  : eq<T,long>()   ? ct<T,long>(long.Parse(s))
	  : eq<T,double>() ? ct<T,double>(double.Parse(s,System.Globalization.CultureInfo.InvariantCulture))
	  : eq<T,char>()   ? ct<T,char>(s[0])
					   : ct<T,string>(s);
	public static string[] RM<T>(out T a) {
		var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries); 
		a = cv<T>(z[0]);
		return z;
	}
	public static string[] RM<T,U>(out T a,out U b) {
		var z = RM<T>(out a); 
        b = cv<U>(z[1]);
		return z;
	}
	public static string[] RM<T,U,V>(out T a,out U b,out V c) {
		var z = RM<T,U>(out a,out b); 
        c = cv<V>(z[2]);
		return z;
	}
	public static string[] RM<T,U,V,W>(out T a,out U b,out V c,out W d) {
		var z = RM<T,U,V>(out a,out b,out c); 
        d = cv<W>(z[3]);
		return z;
	}
	public static string[] RM<T,U,V,W,X>(out T a,out U b,out V c,out W d,out X e) {
		var z = RM<T,U,V,W>(out a,out b,out c,out d); 
        e = cv<X>(z[4]);
		return z;
	}
	public static string[] RM<T,U,V,W,X,Y>(out T a,out U b,out V c,out W d,out X e,out Y f) {
		var z = RM<T,U,V,W,X>(out a,out b,out c,out d,out e); 
        f = cv<Y>(z[5]);
		return z;
	}
	public static string[] RA<T>(out T[] a) {		
		var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries);
		a = z.Select(cv<T>).ToArray();
		return z;
	}
	public static string[][] RL<T>(long n,out T[] a) {
		a = new T[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) y[i] = RM(out a[i]);
		return y;
	}
	public static string[][] RL<T,U>(long n,out VT<T,U>[] a) {
		a = new VT<T,U>[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) {
			T o; U p;
			y[i] = RM(out o,out p);
			a[i] = new VT<T,U>(o,p);
		}
		return y;
	}
	public static string[][] RL<T,U,V>(long n,out VT<T,U,V>[] a) {
		a = new VT<T,U,V>[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) {
			T o; U p; V q;
			y[i] = RM(out o,out p,out q);
			a[i] = new VT<T,U,V>(o,p,q);
		}
		return y;
	}
	public static string[][] RL<T,U,V,W>(long n,out VT<T,U,V,W>[] a) {
		a = new VT<T,U,V,W>[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) {
			T o; U p; V q; W r;
			y[i] = RM(out o,out p,out q,out r);
			a[i] = new VT<T,U,V,W>(o,p,q,r);
		}
		return y;
	}
	public static string[][] RX<T>(long n,out T[][] a) {
		a = new T[n][];
		var y = new string[n][];
		for(int i=0;i<n;i++) y[i] = RA(out a[i]);
		return y;
	}

	static void wwp(Action act){
		var s = new Prt(Console.OpenStandardOutput()){AutoFlush = false};
		Console.SetOut(s);
		act();
		Console.Out.Flush();
		s.AutoFlush = true;
		Console.SetOut(s);
	}
	[MethodImpl(256)]
	static string wfm(Type t) =>t.Equals(typeof(double)) ? "{0:F10}" : "{0}";
	public static void WM(params object[] a) {
		wwp(()=>{
			for(int i=0;i<a.Length;i++) {
				var f = wfm(a[i].GetType()) + ((i<a.Length-1) ? " " : Environment.NewLine);
				Console.Write(f,a[i]);
			}
		});
	}
	public static void WA<T>(IList<T> a) {
		wwp(()=>{
			var f = wfm(typeof(T));
			var g = f + " ";
			var h = f + Environment.NewLine;
			for(int i=0;i<a.Count;i++) Console.Write(((i<a.Count-1) ? g : h),a[i]);
		});
	}
	public static void WL<T>(IList<T> a) {
		wwp(()=>{
			var f = wfm(typeof(T)) + Environment.NewLine;
			foreach(T x in a) Console.Write(f,x);
		});
	}


}

#endregion


}

Submission status: Runtime Error

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

l = 0
r = max(H)

while r > l+1:
    T = (l+r)//2
    c = 0
    for h in H:
        if h > B*T:
            c += (h-B*T)//(A-B)
            if (h-B*T)%(A-B) != 0:
                c += 1
    if c <= T:
        r = T
    else:
        l = T

if l == T:
    print(T+1)
else:
    print(T)

Submission status: Runtime Error

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

left = 1
right = max(h)//A + 1
import math
def judge(x):
    cnt = 0
    tmp = 0
    for i in range(N):
        tmp = h[i] - B * x
        if tmp > 0:
            cnt += math.ceil(tmp/(A-B))
    if cnt <= x:
        return True
    else:
        return False
    
def binary(left,right):
    c = (left + right)//2
    if left >= right:
        for i in range(3):
            idx = left -1 + i
            if judge(idx):
                return (idx)
    if judge(c):
        right = c -1
        return binary(left,right)
    else:
        left = c + 1
        return binary(left,right)
    
    
ans = binary(left,right)
print(ans)

Submission status: Runtime Error

Solution code:
a,b,c = map(int, input().split())
l = [int(input()) for _ in range(a)]
flag = True
l = sorted(l)
max_T = 10**18
def ok(k):
    s = k
    for i in l:
        hp = i - c * k
        if hp > 0:
            s -= -(-hp // (b - c))
        if s < 0:
            return False
    return True
def binary_search(l,r):
    mid = (l + r) // 2
    if l == r:
        return l
    elif ok(mid):
        return bbb(l,mid)
    else:
        if mid == l:
            mid += 1
            
        return bbb(mid,r)
ans =binary_search(0,max_T)
print(ans)

Submission status: Runtime Error

Solution code:
a,b,c = map(int, input().split())
l = [int(input()) for _ in range(a)]
flag = True
l = sorted(l)
max_T = 10**18
def ok(k):
    s = k
    for i in l:
        hp = i - c * k
        if hp > 0:
            s -= -(-hp // (b - c))
        if s < 0:
            return False
    return True
def binary_search(l,r):
    mid = (l + r) // 2
    if l == r:
        return l
    elif ok(mid):
        return bbb(l,mid)
    else:
        if mid == l:
            mid += 1
            
        return bbb(mid,r)
binary_search(0,max_T)

Submission status: Runtime Error

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

ok=max(H)//B+1
ng=0
mid=(ok+ng)//2
while ok-ng>1:
  cntlive=0
  for h in H:
    h-=B*mid
    if h>0:
      cntlive+=1
  if cntlive<=mid:
    ok=mid
  else:
    ng=mid
  mid=(ok+ng)//2
print(ok)

Submission status: Runtime Error

Solution code:

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1e9
#define PI acos(-1)
typedef long long ll;
typedef pair<int, int> p_ii;

int n, a, b;
int h[100010];

bool enough(ll t) {
	ll times = 0;
	for (int i = 0; i < n; i++) {
		if (h[i] - b * t < 0)continue;
		times += ((h[i] - b * t) + (a - b - 1)) / (a - b);
	}
	return times <= t;
}

int main() {
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++)cin >> h[i];

	ll left = 0, right = INF;
	while (right - left > 1) {
		ll mid = (left + right) / 2;
		if (!enough(mid))left = mid;
		else right = mid;
	}

	cout << right << endl;

	return 0;
}

Submission status: Runtime Error

Solution code:
N, A, B = map(int,input().split())
h = [0 for i in range(N)]
for i in range(N):
	h[i] = int(input())
h = sorted(h)
# import math
# N, A, B = 4, 5, 3
# h = [8,7,4,2]
# h = sorted(h,reverse=True)

def enough(T):
	tmp = 0
	for i in range(N):
		if h[i] >= B*T:
			tmp += math.ceil((h[i]-B*T)/(A-B))
	return True if tmp <= T else False

MAX = 10**9
MIN = 0
while MAX > MIN:
	if enough(MAX) == True and enough(MIN) == False and MAX - MIN == 1:
		break
	MID = (MAX+MIN)//2
	if enough(MID) == True:
		if enough(MID-1) == True:
			MAX = MID-1
		else:
			MAX = MID
	else:
		if enough(MID+1) == False:
			MIN = MID+1
		else:
			MIN = MID
print(MAX)

Submission status: Runtime Error

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

tekis = teki.sort()


while len(tekis) > 0:
    tekis[-1] = tekis[-1] - a
    if len(tekis) >= 2:
        for i in range(len(tekis) -1):
            tekis[i] = tekis[i] - b
    tekis = list(sorted(tekis))
    for i in range(len(tekis)):
        if tekis[i] <= 0:
            tekis[i] = 0
    while 0 in tekis:
        tekis.remove(0)
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n , a, b = map(int,input().split())
teki = []
ans = 0
for i in range(n):
    teki.append(int(input())
    
tekis = list(sorted(teki))


while len(tekis) > 0:
    tekis[-1] = tekis[-1] - a
    if len(tekis) >= 2:
        for i in range(len(tekis) -1):
            tekis[i] = tekis[i] - b
    tekis = list(sorted(tekis))
    for i in range(len(tekis)):
        if tekis[i] <= 0:
            tekis[i] = 0
    while 0 in tekis:
        tekis.remove(0)
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n , a, b = map(int,input().split())
teki = []
ans = 0
for i in range(n):
    teki.append(input())
    
tekis = list(sorted(teki))

while len(tekis) > 0:
    tekis[-1] = tekis[-1] - a
    if len(tekis) >= 2:
        for i in range(len(tekis) -1):
            tekis[i] = tekis[i] - b
    tekis = list(sorted(tekis))
    for i in range(len(tekis)):
        if tekis[i] <= 0:
            tekis[i] = 0
    while 0 in tekis:
        tekis.remove(0)
    ans += 1
print(ans)

Submission status: Runtime Error

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)