Under construction

Still being built. Things may change

Misère

Interview

Time limit2sMemory limit2048 MB

Summary
Given n cards in a hand from an A-by-B deck, find the fewest cards to swap so that every suit meets the misère condition.
Level

Medium4 of 10

Topics
Greedy, Sorting, Array
Solved
No attempts yet

Problem

Préférence is a card game that is very popular in Eastern Europe. It is usually played with a 32-card deck: pip cards from 7 to 10, Jack, Queen, King, and Ace in each of four suits, Spades, Clubs, Diamonds, and Hearts. Each round, three players receive ten cards each, and two cards are left on the table as the talon. Then comes an auction, where players make bids. A bid is an obligation to take at least a certain number of tricks. A special bid is a misère, an obligation to take no tricks no matter how the other players play.

Problem

This task uses a modified version of préférence played with a deck of A×BA \times B cards, where AA is the number of suits and BB is the number of ranks in each suit. The standard 32-card deck has A=4A = 4 suits and B=8B = 8 ranks. Suits are numbered 1 to AA, and ranks are numbered 1 to BB.

A misère is guaranteed if, for every suit, the cards of that suit in your hand, sorted by rank as b1<b2<⋯<bkb_1 < b_2 < \cdots < b_k (where kk is the number of cards of that suit in your hand), satisfy bi≤2i−1b_i \le 2i - 1 for all ii from 1 to kk. If you have no cards of a suit (k=0k = 0), the condition holds trivially.

You have nn cards in your hand. You may choose any xx cards you do not have and add them to your hand. Then you must choose any xx of your n+xn + x cards and drop them, leaving nn cards in your hand. Find the smallest xx for which you can turn your hand into a guaranteed misère.

Examples1

  1. Example 1

    Input
    2
    4 2 6
    1 1
    1 2
    1 6
    2 3
    2 4 5
    3 4
    2 4
    
    Expected output
    1
    2