Misère
InterviewTime limit2sMemory limit2048 MB
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.
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 cards, where is the number of suits and is the number of ranks in each suit. The standard 32-card deck has suits and ranks. Suits are numbered 1 to , and ranks are numbered 1 to .
A misère is guaranteed if, for every suit, the cards of that suit in your hand, sorted by rank as (where is the number of cards of that suit in your hand), satisfy for all from 1 to . If you have no cards of a suit (), the condition holds trivially.
You have cards in your hand. You may choose any cards you do not have and add them to your hand. Then you must choose any of your cards and drop them, leaving cards in your hand. Find the smallest for which you can turn your hand into a guaranteed misère.