Module c
Expand description
ยงABC 358 C - Popcorn
refs: https://atcoder.jp/contests/abc358/tasks/abc358_c
use std::{cmp::min, collections::HashSet};
use proconio::input;
fn satisfy(combination: u32, s: &[String], m: usize) -> bool {
let mut popcorns = HashSet::new();
for (ni, pops) in s.iter().enumerate() {
if combination & (1 << ni) > 0 {
for (idx, pop) in pops.chars().enumerate() {
if pop == 'o' {
popcorns.insert(idx);
}
}
}
}
popcorns.len() == m
}
fn main() {
input! {
n: usize,
m: usize,
s: [String; n],
}
let mut ans = 100;
for combination in 0..(1 << n) {
if satisfy(combination, &s, m) {
ans = min(ans, combination.count_ones());
}
}
println!("{}", ans);
}