Overview

This problem asks whether a school trip group leader can distribute \(K\) snacks each to \(N\) members, given inventory constraints on \(M\) types of purchased snacks.

Analysis

A naive approach requires the total number of snacks to be at least \(N \times K\), but that alone is insufficient. The key observation is the constraint that you cannot give two or more snacks of the same type to the same member. In other words, each type of snack can be distributed to at most \(N\) people, but we need to think about the constraints more deeply.

Specifically, since each member receives \(K\) different types of snacks, even if there are many snacks of a certain type, at most \(N\) of them can be utilized. However, when there are \(K\) or more types of snacks, since the \(K\) snacks each member receives must be of different types, the upper limit for distributing the same type of snack to multiple members is \(N\), but additional constraints also arise.

In particular, since each member receives \(K\) snacks, for \(K\) types of snacks we can distribute up to \(N\) of each. However, for types beyond the top \(K\), since each member already receives \(K\) snacks, no more can be distributed to them (meaning at most \(N-1\) can be distributed). We need to determine whether the inventory can be efficiently distributed considering this constraint.

Algorithm

1. First, check whether the total number of snacks is at least \(N \times K\). If insufficient, the answer is clearly “No”.
2. Next, sort the snack types in descending order of quantity.
3. For the sorted list of snacks, assume that the top \(K\) types can distribute up to \(N\) each, and the remaining types can distribute up to \(N-1\) each. Calculate the total number of distributable snacks.
4. If this total is at least \(N \times K\), output “Yes”; otherwise, output “No”.

This approach efficiently captures the constraint that when each member receives \(K\) snacks, the most abundant snacks are prioritized for distribution up to \(N\) each, while the remaining snacks can only be distributed up to \(N-1\) each.

Complexity

• Time complexity: \(O(M \log M)\) (dominated by sorting the snack types)
• Space complexity: \(O(M)\) (storing the snack list)

Implementation Notes

• Since input values can be large, be careful about overflow when computing the total sum (Python does not have integer overflow, but other languages require caution).

• It is important to sort the snack list in descending order and handle the top \(K\) types separately from the rest.

• For each snack type, computing the distributable upper limit as min(C[i], N) or min(C[i], N-1) properly handles cases where inventory exceeds demand.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print("No")
        return
        
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    C = list(map(int, data[3:3+M]))
    
    total_needed = N * K
    
    if sum(C) < total_needed:
        print("No")
        return
        
    max_per_kind = N
    C.sort(reverse=True)
    
    total_available = 0
    for i in range(M):
        if i < K:
            total_available += min(C[i], N)
        else:
            total_available += min(C[i], N - 1)
            
    if total_available >= total_needed:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.