Overview

This is a problem to determine whether it is possible to distribute exactly \(K\) snacks (all of different types) to each of \(N\) members from \(M\) types of snacks. We can determine whether distribution is possible while respecting the quantity limit of each type using a simple conditional expression.

Analysis

Modeling the Problem

Organizing this problem, it becomes the following assignment problem:

• For each of the \(N\) members, select \(K\) types from \(M\) types and give them 1 of each
• Since there are only \(C_i\) snacks of type \(i\), they can be distributed to at most \(C_i\) people

This can be viewed as a bipartite graph matching (flow problem). Place \(N\) members on the left side and \(M\) types of snacks on the right side, and draw edges from each member to all types. Each node on the member side has degree exactly \(K\), and the node for type \(i\) has maximum degree \(C_i\).

Key Insight: Symmetry

All members are completely symmetric in the sense that they are “connected to all \(M\) types of snacks.” In other words, every member has the same set of choices.

In such a symmetric structure, the only bottleneck is whether there are enough snacks overall. Specifically:

• There are \(C_i\) snacks of type \(i\), but since each member can receive at most 1, the contribution of type \(i\) to the \(N\) people is \(\min(C_i, N)\).
• If the total contribution across all types \(\sum_{i=1}^{M} \min(C_i, N)\) is at least the required total distribution count \(N \times K\), then distribution is possible.

Why This Is Sufficient

This can be explained using the max-flow min-cut theorem from flow theory. Draw edges with capacity \(K\) from the source to each member, edges with capacity \(1\) from each member to all types, and edges with capacity \(C_i\) from each type to the sink.

Since the member side is completely symmetric, when considering the minimum cut, the tightest constraint occurs when all members are included. In this case, the capacity on the sink side becomes \(\sum \min(C_i, N)\), and if this is at least \(N \times K\), the maximum flow reaches \(N \times K\).

Concrete Example

For \(N=3, M=3, K=2, C=[2, 3, 1]\):

• \(\min(2,3) + \min(3,3) + \min(1,3) = 2 + 3 + 1 = 6\)
• \(N \times K = 3 \times 2 = 6\)
• \(6 \geq 6\), so Yes

Algorithm

1. For each \(C_i\), compute \(\min(C_i, N)\) and find the total sum
2. If the sum is at least \(N \times K\), output Yes; otherwise output No

Complexity

• Time complexity: \(O(M)\) (just compute \(\min(C_i, N)\) for each type and sum them up)
• Space complexity: \(O(M)\) (for storing the input)

Implementation Notes

• Since both \(N\) and \(K\) can be up to \(10^9\), \(N \times K\) can reach \(10^{18}\). In Python, arbitrary-precision integers are standard so there is no worry about overflow, but in C++ and similar languages, you need to use long long.

• Be careful not to forget the \(\min(C_i, N)\) computation — omitting it would correspond to an invalid calculation where the same type is given more than once to a single person.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    C = [int(input_data[3 + i]) for i in range(M)]
    
    # Each member gets exactly K candies, all different types.
    # Each type i can be given to at most C_i members (and at most 1 per member).
    # We need to assign to N members, K types each, such that type i is used at most C_i times.
    
    # This is equivalent to: does there exist a bipartite graph between N members and M types,
    # where each member has degree exactly K, and each type i has degree at most C_i?
    
    # By Hall's theorem / deficiency version, this is possible if and only if:
    # sum(min(C_i, N)) >= N * K
    # 
    # But we also need K <= M (given by constraints).
    # 
    # Actually, let me think more carefully. We need to check if a bipartite graph exists
    # where one side has N nodes each with degree K, and the other side has M nodes where
    # node i has degree at most C_i.
    #
    # By the Gale-Ryser theorem (or flow arguments), the necessary and sufficient condition is:
    # 1) sum(min(C_i, N)) >= N * K
    # 2) K <= M
    #
    # Condition 2 is guaranteed by constraints.
    #
    # Let me verify condition 1 is sufficient. We can think of it as a flow problem:
    # source -> each member with capacity K, each member -> each type with capacity 1,
    # each type -> sink with capacity C_i. Max flow = N*K iff sum(min(C_i, N)) >= N*K.
    # 
    # Actually, for the max flow to be N*K, we need:
    # - For every subset S of members, the neighborhood capacity is enough.
    # By symmetry (all members are identical in terms of connectivity - each connects to all M types),
    # the binding constraint is the full set: sum(min(C_i, N)) >= N*K.
    # Also each member can get at most M types, so K <= M is needed.
    
    total = 0
    for i in range(M):
        total += min(C[i], N)
    
    if total >= N * K:
        print("Yes")
    else:
        print("No")

solve()

---

This editorial was generated by claude4.6opus-thinking.