Official

B - Full House 3 Editorial by en_translator


Solution 1. Inspect all combinations of five cards

We try to enumerate all the combinations of five cards chosen out of seven.
There are several ways to implement it; this time, we introduce bitwise exhaustive search.
The explanation of bitwise exhaustive search can be found in articles like the following. (These are all in Japanese.)
bit 全探索
bit全探索について簡単にまとめる
APG4b - AC - 3.05.ビット演算

For each of the seven cards, determine each card is chosen or not, and check whether the following conditions are satisfied:

  • Exactly five cards are chosen.
    • This can be checked by counting standing bits.
  • The chosen cards form a full house.
    • This can be checked by, for example, sorting the chosen cards \(B_1,B_2,\dots,B_5\) and checking if one of the following conditions can be satisfied:
      • \(B_1=B_2=B_3 \neq B_4=B_5\)
      • \(B_1=B_2 \neq B_3=B_4=B_5\)

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

bool isFull(vector<int> &b){
  sort(b.begin(),b.end());
  if(b[0]==b[1] && b[1]==b[2] && b[2]!=b[3] && b[3]==b[4]){return true;}
  if(b[0]==b[1] && b[1]!=b[2] && b[2]==b[3] && b[3]==b[4]){return true;}
  return false;
}

int main(){
  vector<int> a(7);
  for(auto &nx : a){cin >> nx;}
  for(int i=0;i<(1<<7);i++){
    vector<int> b;
    for(int j=0;j<7;j++){
      if(i&(1<<j)){b.push_back(a[j]);}
    }
    if(b.size()==5){
      sort(b.begin(),b.end());
      if(isFull(b)){
        cout << "Yes\n";
        return 0;
      }
    }
  }
  cout << "No\n";
  return 0;
}

Solution 2. Rephrase the condition on the full house can be formed

First, count how many cards with each integer there are. Then, a full house can be formed if and only if:

  • there are at least three cards with an integer \(x\) written on it; and
  • there are at least two cards with another integer \(y\) with \(x \neq y\) written on it.

This can be checked by sorting the cards by the frequencies, and checking if

  • the most frequent cards occur three more times, and
  • the second most frequent cards occur two more times, and

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  vector<int> bk(13,0);
  for(int i=0;i<7;i++){
    int x;
    cin >> x;
    bk[x-1]++;
  }
  sort(bk.rbegin(),bk.rend());
  if(bk[0]>=3 && bk[1]>=2){cout << "Yes\n";}
  else{cout << "No\n";}
  return 0;
}

posted:
last update: