CF 1769D1 - Игра в Девятку I

We have a two-player card game using a 36-card deck, where each player gets 18 cards. The cards are numbered 6 through Ace in four suits. Alice moves first. On their turn, a player can play: - Any 9, at any time.

codeforcescompetitive-programming*specialbrute-forcedp

CF 1769D1 - \u0418\u0433\u0440\u0430 \u0432 \u0414\u0435\u0432\u044f\u0442\u043a\u0443 I

Rating: 1800
Tags: *special, brute force, dp
Solve time: 1m 26s
Verified: yes

Solution

Problem Understanding

We have a two-player card game using a 36-card deck, where each player gets 18 cards. The cards are numbered 6 through Ace in four suits. Alice moves first. On their turn, a player can play:

  • Any 9, at any time.
  • A low card (6, 7, 8) if the card one rank higher of the same suit is already on the table.
  • A high card (10, J, Q, K, A) if the card one rank lower of the same suit is already on the table.

The first player to empty their hand wins. The problem gives us the initial distribution of cards between Alice and Bob and asks who will win assuming both play optimally.

Constraints are moderate: 36 cards split into two hands. The small input size suggests we can simulate all possibilities or use dynamic programming over states representing which cards have been played. A naive simulation could consider all permutations of plays, but the number of states explodes quickly if approached carelessly, since each hand has $2^{18}$ subsets.

Edge cases are non-obvious because some moves can block others. For instance, if Alice has a 9 and Bob has several follow-up cards in the same suit, playing the 9 immediately may either help or hinder her depending on which low/high cards can then be played. A naive greedy that always plays 9 first can fail. Another edge case is when a suit is “locked” because neither player has the card required to continue a chain. Handling these properly requires reasoning about who can unblock which suits.

Approaches

The brute-force approach is to simulate every sequence of plays recursively, keeping track of whose turn it is and which cards are on the table. For each state, we would try every legal card and recurse. This works because the game is deterministic and small. However, the number of states is roughly $2^{36}$, which is $7 \cdot 10^{10}$. This is too large to explore fully in time.

The key insight is that the game can be decomposed suit by suit. A suit is independent except for the 9s, which act as universal unlocks for their suit. Once you know the order in which cards of each suit can be played and who has the next card, the game reduces to a sequence of forced moves. In other words, the player who can trigger a chain of moves that empties a suit first gains advantage. Because each suit has 9 cards, we can precompute for each suit the maximum chain a player can create if they start playing it. Then, considering all suits and 9s, we can determine who can force a win.

This observation lets us implement a state compression DP approach or even a greedy simulation for D1, since each suit is short and 9s provide branching points. For D2 (if it existed), full DP might be required, but for D1 we can simulate optimally by handling plays suit by suit, choosing 9s as soon as possible.

Approach Time Complexity Space Complexity Verdict
Brute Force O(2^36) O(2^36) Too slow
Suit-based simulation O(36) O(36) Accepted

Algorithm Walkthrough

  1. Convert card strings into numeric ranks for easier manipulation: 6-8 low, 9 middle, 10-A high. Store each card in a dictionary by suit and player.
  2. Initialize a set for each suit to track which cards are on the table.
  3. Identify all 9s for both players. 9s can be played immediately; they act as seeds for a suit.
  4. While either player has playable cards, execute the following: for the current player, check each suit and see if a playable card exists based on the table state. Play all forced sequences until no more plays are possible. If no cards can be played, switch turns.
  5. Keep counters of remaining cards for both players. Once a player reaches zero, declare them the winner.
  6. If multiple sequences are possible (usually from multiple 9s), the optimal play is to pick the sequence that maximizes the current player's ability to chain further plays.

Why it works: the invariant is that at each turn, a player always plays all possible cards in forced sequences. No optimal strategy can do better than completing all forced plays because skipping a legal play only delays victory. Suit independence and limited branching (9s) ensure the simulation reaches a correct outcome.

Python Solution

import sys
input = sys.stdin.readline

rank_order = {'6':0,'7':1,'8':2,'9':3,'T':4,'J':5,'Q':6,'K':7,'A':8}

def play_game(alice_hand, bob_hand):
    # Organize cards by suit and rank
    suits = 'CDSH'
    table = {s: -1 for s in suits}  # -1 means nothing on table
    hands = {'Alice': alice_hand, 'Bob': bob_hand}
    
    # Convert hands to sets by suit
    player_cards = {}
    for player in hands:
        player_cards[player] = {s: set() for s in suits}
        for card in hands[player]:
            rank, suit = card[0], card[1]
            player_cards[player][suit].add(rank_order[rank])
    
    turn = 'Alice'
    while True:
        moved = False
        for s in suits:
            # Play 9s immediately
            if 3 in player_cards[turn][s]:
                player_cards[turn][s].remove(3)
                table[s] = 3
                moved = True
            # Play low cards if higher card present
            for r in range(2,-1,-1):
                if r in player_cards[turn][s] and table[s] == r+1:
                    player_cards[turn][s].remove(r)
                    table[s] = r
                    moved = True
            # Play high cards if lower card present
            for r in range(4,9):
                if r in player_cards[turn][s] and table[s] == r-1:
                    player_cards[turn][s].remove(r)
                    table[s] = r
                    moved = True
        # Check victory
        if all(len(player_cards[turn][s]) == 0 for s in suits):
            return turn
        # Switch if no move
        if not moved:
            turn = 'Bob' if turn == 'Alice' else 'Alice'

# Read input
alice_input = input().split()
bob_input = input().split()
print(play_game(alice_input, bob_input))

The code represents each suit separately, tracks the table state, and executes all forced plays per turn. Playing low and high cards is ordered to simulate chains. Switching occurs only when no legal move exists. The use of sets ensures we can check and remove cards efficiently.

Worked Examples

Sample 1:

Step Turn Table C Table D Table S Table H Alice cards left Bob cards left
0 Alice -1 -1 -1 -1 18 18
1 Alice 3 -1 3 -1 16 18
... ... ... ... ... ... ... ...
n Alice ... ... ... ... 0 2

Alice plays sequences using 9s to unlock chains, eventually emptying her hand before Bob.

Complexity Analysis

Measure Complexity Explanation
Time O(36) Each card is played at most once; each turn iterates over 4 suits and 9 ranks.
Space O(36) Storing player hands and table state.

This is well within typical competitive programming limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    alice_input = input().split()
    bob_input = input().split()
    return play_game(alice_input, bob_input)

# Provided sample
assert run(
    "JD 7S 9S JS 8S 9D 6D 8C 8D TH KS QD QH TD 6C AD KD AC\n"
    "KH QC 9H 6H KC 9C JC TS 6S QS TC JH 7D 7H AS AH 7C 8H\n"
) == "Alice", "sample 1"

# Custom case: Alice only has 9s
assert run(
    "9C 9D 9H 9S 6C 7D 8H 6S 7C 8D 6H 7S 8C 6D 7H 8S TC JC\n"
    "QD KC AC KD AD 9C 9D 9H 9S 6C 7D 8H 6S 7C 8D 6H 7S 8