Determine winner in stack-merging game

Problem Statement

Two players play a game with n stacks of coins, where the i-th stack contains c[i] coins. In each turn, a player must choose two stacks with sizes a and b and merge them into a single stack of size a + b. However, this merge is only valid if the new size a + b is less than or equal to a given limit K.

The game ends when no more valid merges can be made (i.e., for all pairs of stacks, the sum of their sizes exceeds K). The last player to make a valid move wins. Given an array c of stack sizes and an integer K, determine if the first player wins assuming optimal play. Assume both players play perfectly.

Function Signature

def can_first_player_win(c: List[int], K: int) -> bool:

Constraints

• n (number of stacks) is between 1 and 10.
• c[i] is between 1 and K.
• K is between 1 and 100.

Examples

Example 1: Input: c = [2, 2, 2], K = 5 Output: True Explanation: Player 1 merges two 2s into a 4. The stacks are now [4, 2]. Player 2 cannot merge 4 and 2 because 4+2 > 5. Player 1 wins.

Example 2: Input: c = [3, 3], K = 5 Output: False Explanation: No two stacks can be merged because 3+3 > 5. Player 1 has no moves and loses immediately.