Problem:


Score : 500 points

Problem Statement

We have N logs of lengths A_1,A_2,\cdots A_N.

We can cut these logs at most K times in total. When a log of length L is cut at a point whose distance from an end of the log is t (0<t<L), it becomes two logs of lengths t and L-t.

Find the shortest possible length of the longest log after at most K cuts, and print it after rounding up to an integer.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq K \leq 10^9

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

Print an integer representing the answer.

Sample Input 1

2 3
7 9

Sample Output 1

4

First, we will cut the log of length 7 at a point whose distance from an end of the log is 3.5, resulting in two logs of length 3.5 each.

Next, we will cut the log of length 9 at a point whose distance from an end of the log is 3, resulting in two logs of length 3 and 6.

Lastly, we will cut the log of length 6 at a point whose distance from an end of the log is 3.3, resulting in two logs of length 3.3 and 2.7.

In this case, the longest length of a log will be 3.5, which is the shortest possible result. After rounding up to an integer, the output should be 4.

Sample Input 2

3 0
3 4 5

Sample Output 2

5

Sample Input 3

10 10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

Sample Output 3

292638192



Sample input:
2 3
7 9


Sample output:
4

Submission status: Accepted

Solution code:
from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
try:
  up, lo = ceil(sum(A) / K), 0
  while up - lo > 1:
    mid = (up+lo) // 2
    cnt = 0
    for a in A:
      cnt += ceil(a / mid)-1
    if cnt > K:
      lo = mid
    else:
      up = mid
  print(up)
except ZeroDivisionError:
  print(max(A))

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

N, K = MI()
mylist = LI()
length = len(mylist)

high = max(mylist)+1
low = 0
mid = (high + low) / 2

while high - low >= 0.001:
    temp = 0
    for i in mylist:
        if i % mid == 0:
            temp += (i // mid) - 1
        else:
            temp += i // mid
    if temp > K:
        low = mid
    else:
        high = mid
    mid = (high + low) / 2

result = math.ceil(low)


num2 = result+10**(-8)
temp= 0
for i in mylist:
    if i % num2 == 0:
        temp += (i // num2) - 1
    else:
        temp += i // num2
if temp > K:
    print(result+1)
else:
    print(result)

Submission status: Accepted

Solution code:
from math import *
f=lambda:[*map(int,input().split())]
n,k=f()
a=f()
def ok(x):
  c=0
  for i in a:
    c+=ceil(i/x)
  return c<=n+k
l,r=0,10**9
while r-l>1:
  m=(l+r)/2
  if ok(m): r=m
  else: l=m
t=ceil(r)
print(t-ok(t-1) if t>1 else t)

Submission status: Accepted

Solution code:
import sys

N, K = map(int, input().split())
A = list(map(int, input().split()))


def is_ok(x):
    num = 0
    for j in range(N):
        num += (A[j] - 1) // x

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


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


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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
left=1
right=A[-1]
ans=(left+right)//2
if N==1:
    if A[0]%(K+1)==0:
        print(A[0]//(K+1))
    else:
        print(A[0]//(K+1)+1)
else:
    while 1:
        count=0
        for i in range(N)[::-1]:
            if A[i]%ans==0:
                count+=A[i]//ans-1
            else:
                count+=A[i]//ans
            if count>K:
                break
        if count<=K:
            right=ans
        else:
            left=ans
        if right-left<=1:
            break
        ans=(left+right)//2
    for i in range(N):
        if A[i]%left==0:
            count+=A[i]//left-1
        else:
            count+=A[i]//left
        if count>K:
            break
    if count<=K:
        print(left)
    else:
        print(right)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
m=max(arr)
if(k==0):
	print(m)
else:
	low=1
	high=m
	while(low<=high):
		mid=low+(high-low)//2
		if(mid==1):
			print(mid)
			break
		count=0
		count2=0
		for i in range(n):
			count+=(arr[i]-1)//mid
			count2+=(arr[i]-1)//(mid-1)
		if(count<=k and count2>k):
			print(mid)
			break
		elif(count<k or (count<=k and count2<=k+1)):
			high=mid-1
		else:
			low=mid+1

Submission status: Accepted

Solution code:
import sys
from fractions import Fraction
import math
import heapq
input = sys.stdin.readline

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

s = sum(a)

w = [(k * a[i]) // s for i in range(n)]
b = [Fraction((w[i] + 1), a[i]) for i in range(n)]

r = k - sum(w)

heapq.heapify(b)
#print(b)

for i in range(r):
    x = heapq.heappop(b)
    heapq.heappush(b, Fraction(x.numerator+1, x.denominator))

y = heapq.heappop(b)

print(math.ceil(Fraction(y.denominator, y.numerator)))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
As = list(map(int, input().split()))


def solve(t):
    count = 0
    for a in As:
        if a % t == 0:
            count += a // t - 1
        else:
            count += a // t
    if count <= k:
        return True
    else:
        return False


def main(l, r):
    if r - l == 1:
        print(r)
    else:
        m = (l + r) // 2
        if solve(m):
            r = m
            return main(l, r)
        else:
            l = m
            return main(l, r)

if solve(1):
  print('1')
else:
  main(1, max(As))

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
def dhondt(Votes, n_seats):
    # ドント方式  候補者数 N に対して O(NlogN)
    n_candidates = len(Votes)
    sum_votes = sum(Votes)
    S0 = []  # 端数切り捨てによってすぐ確定できる席数
    C = []
    for i, v in enumerate(Votes):
        s0 = n_seats*v//sum_votes
        S0.append(s0)
        for s in range(s0+1, s0+10000):
            if s*sum_votes >= v*(n_seats+n_candidates):
                break
            C.append((s/v, i))
        else:
            assert False
    C.sort(key=itemgetter(0))
    S = S0[:]
    for _, i in C[:n_seats-sum(S0)]:
        S[i] += 1
    return S0, S


input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
sum_A = sum(A)
S0, S = dhondt(A, K)
ans = 0
for s, a in zip(S, A):
    ans = max(ans, -(-a//(s+1)))
print(ans)

Submission status: Accepted

Solution code:
from math import *
f=lambda:[*map(int,input().split())]
n,k=f()
a=f()
def ok(x):
  c=0
  for i in a:
    c+=ceil(i/x)
  return c<=n+k
l,r=0,10**9+1
while r-l>0.1:
  m=(l+r)/2
  if ok(m): r=m
  else: l=m
t=ceil(r)
print(t-ok(t-1) if t>1 else t)

Submission status: Accepted

Solution code:
from math import ceil

N, K = map(int, input().split())
A = [*map(int, input().split())]

l_lb, l_min = 0, max(A)
while l_min - l_lb > 1:
  l_mid = (l_lb + l_min) // 2
  if sum(ceil(a/l_mid) for a in A) - N > K:
    l_lb = l_mid
  else:
    l_min = l_mid
print(l_min)

Submission status: Accepted

Solution code:
from math import ceil
n,k=map(int,input().split())
lst=list(map(int,input().split()))
ng=0
ok=10**9+1
while ok-ng>1:
    mid=(ok+ng)//2
    tmp=0
    for i in range(n):
        tmp+=ceil(lst[i]/mid)-1
    if tmp>k:
        ng=mid
    else:
        ok=mid
print(ok)

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    import math
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    l,r=0,a[-1]
    while math.ceil(r)>math.ceil(l):
        x=(l+r)/2
        cnt=0
        for i in a:
            if i%x==0:
                cnt+=i//x-1
            else:
                cnt+=i//x
        if cnt>k:
            l=x
        else:
            r=x
    print(math.ceil(l))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import math
import heapq
n,k=map(int,input().split())
a=list(map(int,input().split()))
SUM=sum(a)
ans=[]
y=k

for i in range(n):
    x=a[i]*k//SUM
    ans.append([-math.ceil(a[i]/(1+x)),x,i])
    y-=x

heapq.heapify(ans)
#print(y)
#print(ans)
for i in range(y):
    temp=heapq.heappop(ans)
    temp[0]=-math.ceil(a[temp[2]]/(2+temp[1]))
    temp[1]+=1
    heapq.heappush(ans,temp)

temp=heapq.heappop(ans)
print(-temp[0])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

hi = 10**18
lo = 0

while hi - lo > 1:
    mid = (hi + lo) // 2
    cut = 0
    for i in range(N):
        cut += (A[i] + mid - 1) // mid - 1
    if cut <= K:
        hi = mid
    else:
        lo = mid

print(hi)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
if K==0:
  print(max(A))
  exit()
def f(x):
  cnt=0
  for i in A:
    if i%x==0:
      cnt+=i//x-1
    else:
      cnt+=(i//x)
  if cnt<=K:
    return True
  else:
    return False
ok=1
ng=1000000000
for i in range(50):
  mid=(ok+ng)//2
  if f(mid):
    ng=mid
  else:
    ok=mid
print(ng)

Submission status: Accepted

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


def kaisuu(moto, shitai):
    return (moto-1) // shitai


def is_ok(arg, dlist, k):
    # 条件を満たすかどうか？問題ごとに定義
    num = map(lambda x: kaisuu(x, arg), dlist)
    return sum(num) <= k


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


def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    print(meguru_bisect(0, 10**9+1, A, k))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split())
    lst=sorted(list(map(int,input().split())))
    
    left=0
    right=lst[-1]
    while right-left>1:
        mid=(right+left)//2
        sm=0
        for x in lst:
            sm+=(x-1)//mid
        
        if sm<=k:
            right=mid
        else : left=mid
    print(right)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
import math
sys.setrecursionlimit(10**6)
MOD = 10**9+7 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = list(map(int,readline().split()))

#2分法
#K回の切断ですべてN以下にできるか
def solve(N):
    cnt = 0
    for a in A:
        if a % N ==0:
            cnt += (a//N-1)
        else:
            cnt += a//N
    if cnt <= K:
        return True
    else:
        return False

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

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N, K = map(int, input().split())
A = list(map(int, input().split()))
# A.sort()
# print(A)

def is_ok(val):
    cnt = 0
    for a in A:
        if a%val == 0:
            cnt += a//val - 1
        else:
            cnt += a//val
    # ls = ([a//val for a in A])
    # print(ls)
    # cnt = sum(ls)
    # print('val, cnt', val, cnt)
    if cnt <= K:
        return True
    else:
        return False

ng = 0
ok = max(A)
while (abs(ok-ng)>1):
    mid = (ok+ng) // 2
    # print(mid, is_ok(mid))
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
    # return ok
print(ok)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def f(X):
    cnt = 0
    for a in A:
        if a <= X:
            continue
        t = a//X
        if t*X == a:
            t -= 1
        cnt += t
    return cnt

l = 1
r = max(A)
while r-l > 0.01:
    m = (r+l)/2
    if f(m) <= K:
        r = m
    else:
        l = m

if int(l) < l:
    print(int(l)+1)
else:
    print(int(l))

Submission status: Accepted

Solution code:
f=lambda:[*map(int,input().split())]
n,k=f()
a=f()
a=[i*100 for i in a]
# Binary Search
def ok(x):
    c=0
    for i in a:
      c+=0--i//x
    return c<=n+k
l,r=0,10**11+1
while r-l>1:
  m=l+r>>1
  if ok(m): r=m
  else: l=m
t=0--r//100
print(t-ok(t-1) if t>1 else t)

Submission status: Accepted

Solution code:

def is_ok(arg):
    cnt = 0 
    for i in range(N):
        cnt += -(-A[i]//arg) - 1
    return K < cnt

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

N,K = map(int, input().split())
A = list(map(int, input().split()))
print(meguru_bisect(max(A)+1, 0)+1)

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def isOK(i, A, K):
    if i == 0:
        return False
    return K >= sum((a-1)//i for a in A)

def b_serach(A, K):
    ng = -1
    ok = 10**9+1

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

    return ok


def main():
    N, K = mi()
    A = list(mi())
    print(b_serach(A, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N,K = map(int, input().split())
A = list(map(int, input().split()))
epsilon = 10**(-5)
#A = [a-epsilon for a in A]

_min = 0
_max = max(A)

while _max - _min > epsilon:
  new = (_min+_max)/2
  if _min < int(new):
    new = int(new)
  times = sum([math.ceil(a/new)-1 for a in A])
  #print(_min, new, _max, times, [math.ceil(a/new)-1 for a in A])
  
  if times <= K:
    _max = new
  else:
    _min = new
  #print(_min, _max)

if  sum([math.ceil(a/_max)-1 for a in A]) <= K:
  print(math.ceil(_max))
else:
  print(math.ceil(_min))

Submission status: Accepted

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

low=1
high=2*max(A)
X=max(A)
while low<=high:
  mid=(low+high)//2
  cnt = 0
  for i in range(N):
      if A[i]%mid==0:
          cnt += A[i]//mid-1
      else:
          cnt += A[i]//mid
  if K<cnt:
    low=mid+1
  else:
    X=min(X,mid)
    high=mid-1
print(X)

Submission status: Accepted

Solution code:
def check(lis,k,mid):
	for i in lis:
		if(i%mid==0):
			k+=1
		k-=(i//mid)
	return k>=0
n,k=map(int,input().split())
lis=list(map(int,input().split()))
a,b=1,max(lis)
ans=b
while(a<=b):
	mid=(a+b)//2
	if(check(lis,k,mid)):
		ans=mid
		b=mid-1
	else:
		a=mid+1
print(ans)

Submission status: Accepted

Solution code:
from math import ceil

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

# a.sort()


l, r = 0, 10**9

while r-l > 1:

    m = (l+r)//2
    c = 0
    for i in range(n):
        if a[i] < m:
            continue
        c += a[i]//m-(a[i] % m == 0)
    # print(c, l, r, m)
    if c > k:
        l = m
    else:
        r = m

print(r)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N, K = LI()
    A = LI()

    maxA = max(A)
    ans = maxA

    left, right = 1, maxA
    mid = (left + right) / 2
    e = 0.000001

    while right - left > e:
        count = 0
        for ai in A:
            count += math.floor(ai / mid)
        if count <= K:
            right = mid
            ans = min(mid, ans)
        else:
            left = mid
        mid = (left + right) / 2

    if math.floor(ans) + e > ans:
        print(math.floor(ans))
    else:
        print(math.ceil(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

#めぐる式二分探索
#indexが条件を満たすか判定
def isOK(mid, A):
  count = 0
  for i in range(N):
    if A[i] > mid:
      xx = A[i] / mid
      if xx % 1 != 0:
        xx += 1
      count += int(xx - 1)
      
  #print("c", count)
  if count > K:
    return False
  else:
    return True
  
#にぶたん
#A : 配列
def binary_search(A):
  N = 10 ** 9
  ng = -1
  ok = N
  while (abs(ok - ng) > 1):
    mid = int((ok + ng) / 2)
    if mid == 0:
      return 1
    #print(ng, ok, mid)
    if isOK(mid, A):
      ok = mid
    else:
      ng = mid
  return ok
  
#a = [1, 14, 32, 51, 51, 51, 243, 419, 750, 910]

print(binary_search(A))

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    _, K = read_ints()
    A = read_ints()
    low, high = 0, max(A)+1
    while high-low > 1:
        mid = low+(high-low)//2
        # max log should be mid
        # 10, maximum log is 4
        required_cuts = sum((a-1)//mid for a in A)
        if required_cuts <= K:
            high = mid
        else:
            low = mid
    return high


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

Submission status: Accepted

Solution code:
def binarySearch(A, K):
    left = 1
    # right = n
    right = max(A)
    while left < right:
        mid = (left + right) // 2
        cost = sum(map(lambda x: (x-1)//mid, A))
        # print(left, right, mid)
        # print(K, cost)
        if K >= cost:
            right = mid
        else:
            left = mid + 1
    # return NOT_FOUND
    # return mid
    
    return left


N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
# print(sorted(A))
print(binarySearch(A, K))