Full House
Time limit2sMemory limit512 MB
Knowing only how many cards were removed from a 52-card deck, find the minimum and maximum number of disjoint full houses (3 of one rank plus 2 of another) that can be formed from the remaining cards.
- Level
Hard8 of 10
- Topics
- Combinatorics, Greedy, Math, Implementation
- Solved
- No attempts yet
Problem
Alex has one deck of playing cards used in poker. The deck has 52 cards, and each card has a suit and a number written on it. The suit is one of spade (♠), club (♣), diamond (♦), heart (♥), and the number is an integer greater than or equal to 1 and less than or equal to 13. No two cards have the same suit and number. That is, the deck has 4×13 = 52 cards. For convenience, a card is written as (suit, number). For example, the 4 of spades is (♠, 4), and the 6 of hearts is (♥, 6).
A full house is a set of 5 cards where three cards have the same integer v1 and the remaining two cards have the same integer v2. Here, v1 and v2 must be different values.
The following five cards form a full house.
- (♠, 1), (♣, 1), (♦, 1), (♠, 2), (♣, 2)
However, the following five cards do not form a full house.
- (♠, 1), (♥, 1), (♠, 2), (♣, 2), (♦, 3)
With one deck of cards, 8 full houses can be made at the same time. Here, each card must be used in only one full house. The following is one of several methods.
- (♠, 1), (♣, 1), (♦, 1), (♠, 13), (♣, 13)
- (♠, 2), (♣, 2), (♦, 2), (♠, 12), (♣, 12)
- (♠, 3), (♣, 3), (♦, 3), (♠, 11), (♣, 11)
- (♠, 4), (♣, 4), (♦, 4), (♠, 10), (♣, 10)
- (♠, 5), (♣, 5), (♦, 5), (♥, 13), (♦, 13)
- (♠, 6), (♣, 6), (♦, 6), (♥, 12), (♦, 12)
- (♠, 7), (♣, 7), (♦, 7), (♥, 11), (♦, 11)
- (♠, 8), (♣, 8), (♦, 8), (♥, 10), (♦, 10)
Not long ago, Bob visited Alex's house and took some of Alex's cards home. Alex does not yet know which cards Bob took, and only knows the number of cards Bob took.
Alex wonders how many full houses can be made at most with the remaining cards. Since Alex does not yet know which cards Bob took, the number of full houses that can be made can vary.
For example, if Alex has only 10 cards and all of them are clubs, the number of full houses that can be made is 0. However, if the 10 cards are (♠, 1), (♠, 2), (♠, 11), (♠, 12), (♣, 2), (♣, 12), (♦, 1), (♦, 2), (♦, 11), (♦, 12), the number of full houses that can be made at the same time is 2, as follows.
- (♠, 1), (♦, 1), (♣, 2), (♠, 2), (♦, 2)
- (♠, 11), (♦, 11), (♣, 12), (♠, 12), (♦, 12)
Knowing only the number of cards Bob took, write a program that finds the minimum and maximum number of full houses that can be made at the same time. Here, intentionally not using cards is not possible, and you must try to make as many full houses as possible.
Input
The first line gives the number of cards Bob took, n (0 ≤ n ≤ 52).
Output
On the first line, print the minimum and maximum number of full houses that can be made at the same time with the remaining cards, separated by a space.