import java.io.BufferedInputStream; import java.util.*; import java.util.stream.IntStream; public class MetroQuizPablo { record State(int asked, int answeredYes) { // asked and answered yes among asked @Override public String toString(){ return "[State " + Integer.toString(asked,2) + " " + Integer.toString(answeredYes,2) + "]"; } } private final int N, M; private final int ALL; private final List metroLineStops; private final HashMap dp; private final HashMap count; MetroQuizPablo(int N, int M, List metroLineStops) { Objects.requireNonNull(metroLineStops); this.N = N; this.ALL = (1<(); count = new HashMap<>(); // precompute probabilities of a state being reachable (just count of how many of the lines) for (var s : metroLineStops) { for (int asked = 0; asked < ALL; asked++) { var answeredYes = asked & s; // we answer truthfully var state = new State(asked,answeredYes); count.merge(state,1,Integer::sum); } } } double solve(State state) { if (!count.containsKey(state)) { // cases with 0 probability need not be treated return 0.0; } if (dp.containsKey(state)) { // answer known return dp.get(state); } var asked = state.asked; var answeredYes = state.answeredYes; int countState = count.get(state); if (countState <= 1) return 0.0; // done double current = countState - 1.0; // worst case we eliminate one possibility per question for (int i = 0; i < N; i++) { var station = 1 << i; if ((station & asked) > 0) continue; var askedAfter = asked | station; var stateYes = new State(askedAfter,answeredYes | station); var stateNo = new State(askedAfter,answeredYes); var countY = count.getOrDefault(stateYes,0); var next = 1 + (countY * solve(stateYes))/countState + ((countState - countY) * solve(stateNo))/countState; if (next < current ) { current = next; } } dp.put(state,current); return current; } public static void main(String[] args) { Scanner scanner = new Scanner(new BufferedInputStream(System.in)); int N = Integer.parseInt(scanner.nextLine()); int M = Integer.parseInt(scanner.nextLine()); var list = IntStream.range(0,M) .mapToObj(__-> Arrays.stream(scanner.nextLine().split("\s+")) .map(Integer::parseInt) .skip(1) // skip number of entries per line .reduce(0,(acc,element)->acc|(1<