Overview

Given a rope of length \(L\), you can cut it at most \(K\) times and distribute rope pieces to as many of the \(N\) students as possible, each requiring a specific length.

Analysis

The key point of this problem is to maximize how many students can receive rope under the constraints that “there is only one rope” and “you can cut it at most \(K\) times.”

Naive Approach and Its Issues

The first idea that comes to mind is to greedily cut and distribute the rope to satisfy the students’ requests \(A_i\).
However, simply distributing in order of largest or smallest requests is not optimal.
Also, depending on how the rope is used, the number of cuts increases, so using binary search to determine “how many people can be satisfied” is effective.

Solution

We fix the answer (the number of people that can be satisfied) and create a function to determine whether that number can truly be satisfied.
Specifically:

• Select \(x\) people with the smallest requests (satisfying people with smaller requests first saves rope)
• If the total of those \(x\) people’s requests exceeds the rope length \(L\), it’s impossible
• Also, satisfying \(x\) people’s requests requires at least \(x - 1\) cuts, so \(x - 1 \leq K\) must hold

By repeating this check with binary search, we find the maximum number of people.

Example

For instance, if \(L = 10\), \(K = 2\), and the requests are [2, 3, 4]:

• Satisfy 2 people: requests [2, 3], total 5, 1 cut → OK
• Satisfy 3 people: requests [2, 3, 4], total 9, 2 cuts → OK
• Therefore, a maximum of 3 people is possible

Algorithm

1. Sort the students’ request list \(A\) in ascending order.
2. Create a determination function can_satisfy(x) for “Can we satisfy \(x\) students?”:
   • Take the \(x\) smallest requests and check whether their total is at most \(L\) and the number of cuts \(x - 1 \leq K\)
3. Using this determination function, find the maximum \(x\) via binary search.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• Immediately return False if the total of requests exceeds the rope length

• Use the fact that the number of cuts equals the number of pieces minus 1

• The binary search range is from 0 to N

  Source Code

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    L = int(data[1])
    K = int(data[2])
    A = list(map(int, data[3:]))

    # ソートして小さい順に処理する
    A.sort()
    
    # 二分探索で最大人数を求める
    def is_possible(x):
        # x人満足させられるか？
        # 大きい方からx個の要求を見て、それらを満たすための最小コスト（必要な切断回数）を計算
        if x == 0:
            return True
        # 要求の大きい方からx個取る
        required = A[N - x:]
        # 各要求を満たすために必要な最小ピース数を貪欲に計算
        pieces = 0
        total_length_used = 0
        for a in required:
            if a > L:
                return False
            # 長さLのロープから長さa以上のピースを何本取れるか
            # 1本のロープから長さaのピースをk本取るには、ロープ長 >= k*a
            # ここでは逆に、長さLのロープから長さaのピースを何本取れるか？
            # max_pieces = L // a
            # しかし、ここでは1つの要求に対して1本のロープが必要
            # 実際には複数の要求を1本のロープから満たせる
            # 貪欲に、ロープをaの長さのピースに切り分ける
            # 1本のロープでaのピースをk本作るには、k*a <= L なら可能
            # つまり、各aに対して必要なロープ本数は ceil(1 / (L//a)) ではない
            # 正しくは、各aを満たすには、1本のロープから最大 floor(L / a) 本のピースが取れる
            # なので、aの要求を1つ満たすのに ceil(1 / (L//a)) ではなく、
            # 単純に1本のロープで何個作れるかを考える必要がある
            
            # しかし、ここでは貪欲に、必要なピース数を計算
            # 各要求aに対して、長さaのピースを1本作る必要がある
            # そのためには、1本のロープから長さaのピースを1本作る
            # このとき、ロープの残りは L - a
            # 次の要求にも使えるか？→ロープは1本だけなので使えない
            # つまり、各要求に対して1本のロープが必要？
            
            # いや、違う。ロープを複数ピースに切って配れる
            # 例えばロープ長6で、要求が2と3なら、
            # 1本のロープを長さ2と3に切って、2人に配れる
            
            # つまり、ある長さのロープを、複数の要求に配れる
            # 要求を大きい順にソートして、貪欲にロープを割り当てていくのが良い
            
            # 最適な方法：
            # 要求を昇順にソートして、小さい方から貪欲にロープを割り当てる
            # ロープを必要な長さだけ使っていく
            # 使用したロープの数と、切断回数をカウントする
            
            pass  # 後で実装
        
        # 改良版アプローチ: 二分探索 + 貪欲
        # x人を満足させることが可能か判定する
        # 要求を小さい順にソート済み A[0], A[1], ..., A[N-1]
        # 満足させたい人数xに対し、A[0] 〜 A[x-1] を満たす必要がある
        # ロープを切断して、これらの要求を満たす最小のロープ本数と切断回数を計算
        
        # しかし、ここではロープは1本だけ
        # 1本の長さLのロープを最大K回切って、最大K+1本のピースを作る
        # これらのピースを使って、要求を満たす
        
        # 要求を昇順にソートしておく
        # 小さい要求から順に、使用可能なピースがあれば割り当てる
        # 使用可能なピースとは、今持っている未使用のピースの中で、要求を満たすもの
        # 最小ヒープを使うと効率的
        
        # しかし、どのピースをどこまで切るかが複雑
        # 別のアプローチ：答えを二分探索する
        # x人を満足可能かどうかを判定する関数を書く
        
        # 判定関数: x人を満足可能か？
        # 要求のうち小さい方からx個を選ぶ（A[0] to A[x-1]）
        # これらを満たすために必要な最小のロープの本数と切断回数を計算
        # ただし、ロープは1本だけ、切断回数は最大K回
        
        # 実際には、ロープを切断して、要求を満たすピースを作る
        # これは複雑なので、別の言い換えを考える
        
        # 重要な観察: 
        # - 要求を昇順にソート
        # - 前から貪欲にロープを割り当て
        # - 1本のロープを使い切るまで使い続ける
        
        # 解法:
        # 二分探索で最大人数を探索
        # 判定部で、x人を満足させるのに必要な最小切断回数 <= K か判定
        
    # 改めて実装
    
    # 要求を昇順にソート
    A.sort()
    
    def can_satisfy(x):
        if x == 0:
            return True
        # 要求の小さい方からx個を満たす必要がある
        required = A[:x]
        # 必要なピース数 = x
        # 1本のロープから最大 floor(L / a) 個のピースが取れるわけではない
        # 実際には、ロープを任意の長さに分割できる
        # つまり、ロープ長Lをいくつかの部分に分割して、それぞれが要求を満たすようにする
        # 分割回数を最小化する必要がある
        
        # これは、ロープを必要な長さのピースに切っていく貪欲法で求められる
        # つまり、必要な長さのリストrequiredに対して、合計がLを超えないグループに分ける
        # 各グループは連続したピースに対応し、グループ数-1が切断回数
        
        # しかし、ここではロープは1本だけ
        # ロープを必要なピースに切るには、必要な長さの合計 <= L でなければならない
        # さらに、切断回数がK以下でなければならない
        
        # 実際には、ロープを必要な長さの和がL以下になるようにグループ分け
        # グループ数を最小化 → 切断回数を最小化
        
        # これは、必要な長さを前から貪欲にロープに詰めていく
        # 新しいロープが必要になるたびにカウントアップ
        # 最終的なロープの本数 - 1 が切断回数（？）
        # いや、ロープは1本だけ
        
        # 正しいアプローチ:
        # 必要な長さのリストrequired = [a0, a1, ..., a_{x-1}]
        # これらの長さのピースを、長さLのロープから作る
        # 1本のロープを必要な長さのピースに切る
        # つまり、1本のロープから複数のピースを切り出す
        # 1本のロープ内で、必要な長さを詰めていく
        # 必要な長さの合計がLを超えた時点で、新しいロープが必要
        # しかし、ロープは1本だけなので、合計 <= L でなければならない
        # その上で、切断回数を最小にするようにロープ内を切る
        
        # 切断回数 = ピース数 - 1 （1本のロープ内での切断）
        # しかし、複数のグループに分けることはできない（ロープは1本）
        
        # よって、条件は:
        # 1. sum(required) <= L
        # 2. 切断回数 <= K where 切断回数 = x - 1 （x個のピースを作るにはx-1回切る）
        # ただし、ロープ内での切断のみを考える
        
        # しかし、ロープは長さLで固定
        # ピースの長さの和がLを超えてはならない
        # また、ロープをx個のピースに分けるにはx-1回の切断が必要
        # つまり、x個のピースを作るのに必要な切断回数はx-1
        
        # しかし、もしロープが十分長ければ、x個のピースは作れる
        # つまり、条件は:
        # 1. sum(required) <= L
        # 2. x - 1 <= K
        
        # これで判定可能
        
        if sum(required) > L:
            return False
        if x - 1 > K:
            return False
        return True
    
    # 二分探索
    left, right = 0, N
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if can_satisfy(mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
            
    print(answer)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.