Overview

Given a single rope of length \(L\) that can be cut at most \(K\) times, the problem asks for the maximum number of students who can participate in crafting, where each student \(i\) requires a minimum rope length of \(A_i\).

Key Observations

There are two important points for solving this problem:

1. Applying a Greedy Approach To distribute rope to as many students as possible, it is optimal to prioritize students who require shorter rope lengths \(A_i\). By giving rope to students who are satisfied with shorter pieces rather than those who need longer ones, the remaining rope can be shared among more people.

2. Considering Two Constraints When distributing rope to students, the following two limits must be satisfied simultaneously:

   • Cut limit: By cutting the rope \(K\) times, the maximum number of pieces produced is \(K+1\). Therefore, the number of students who can receive rope is at most \(\min(N, K+1)\).
   • Total length limit: The total length of distributed rope must not exceed the original rope length \(L\).

Thus, by sorting the required lengths \(A_i\) in ascending order and checking from the beginning whether “the cumulative length does not exceed \(L\)” and “the number of students does not exceed \(K+1\)”, we can derive the answer.

Algorithm

1. Sort the list \(A\) of required lengths for each student in ascending order.
2. Set the upper limit of participants as limit = min(N, K + 1).
3. Check up to limit students starting from the beginning of the sorted \(A\).
4. If the cumulative sum of required lengths of selected students so far is at most \(L\), add that student to the count.
5. Terminate when the cumulative sum exceeds \(L\) or when limit students have been reached, and output the count.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Reading input takes \(O(N)\), sorting list \(A\) takes \(O(N \log N)\), and the subsequent linear scan takes \(O(N)\). Overall, the sorting step dominates the complexity.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the required amounts \(A_i\) for \(N\) students in a list.

Implementation Notes

• Large Input: Since \(N\) can be as large as \(2 \times 10^5\), in Python we use sys.stdin.read().split() to read all input at once for faster I/O.

• Cuts vs. Pieces: Note that \(K\) cuts produce \(K+1\) pieces. Even if the rope length \(L\) is sufficient, it is impossible to distribute rope to more than \(K+1\) students.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # これにより、大量の入力データを高速に処理できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 入力の最初の3つの値（N, L, K）を取得します。
    n = int(input_data[0])
    l = int(input_data[1])
    k = int(input_data[2])
    
    # 各生徒が必要とする最小のロープの長さ A_i をリストとして取得します。
    a = list(map(int, input_data[3:]))
    
    # 少ない長さを必要とする生徒から優先的に配ることで、
    # 工作に参加できる人数を最大化できるため、A_i を昇順にソートします。
    a.sort()
    
    ans = 0
    current_total_length = 0
    
    # ロープを最大 K 回切ることができるため、作れるピースの最大数は K + 1 です。
    # したがって、工作に参加できる生徒の最大人数は、生徒数 N と K + 1 の小さい方になります。
    max_satisfiable_students = min(n, k + 1)
    
    # 条件を満たす生徒の人数を数えます。
    for i in range(max_satisfiable_students):
        # 現在注目している生徒にロープを配ったときの合計の長さが、
        # 持っているロープの総長 L 以下であれば、その生徒に配ることができます。
        if current_total_length + a[i] <= l:
            current_total_length += a[i]
            ans += 1
        else:
            # 合計が L を超える場合は、これ以上生徒に配ることはできません。
            break
            
    # 最大人数を出力します。
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.