// O((N + M) 3^N) with a bottom-up DP that visits all states. // Slower than the O(N M 2^N) solutions. #include #include #include #include #include #include #include #include #include #include using namespace std; uint64_t get_key(uint64_t constraint_locations, uint64_t constraints, int N) { assert(2 * N <= 64); return constraint_locations | (constraints << N); } // https://stackoverflow.com/questions/8281951/bit-hack-to-generate-all-integers-with-a-given-number-of-1s uint64_t bit_twiddle_permute2(uint64_t v) { uint64_t t = (v | (v - 1)) + 1; if (t == 0) { return v >> __builtin_ctz(v); } uint64_t w = t | ((~t & v) >> (__builtin_ctz(v) + 1)); return w; } double solve(int N, const vector &lines) { unordered_map dp; // k is the number of stations with constraints. for (int k = N; k >= 0; --k) { // 'constraint_locations' will cover all subsets of k bits set at // positions in [0, N). for (uint64_t constraint_locations = (1ULL << k) - 1; constraint_locations == 0 || 63 - __builtin_clzl(constraint_locations) < N; constraint_locations = bit_twiddle_permute2(constraint_locations)) { // Iterate over all subsets of 'constraint_locations'. for (uint64_t constraints = constraint_locations;; constraints = (constraints - 1) & constraint_locations) { auto &res = dp[get_key(constraint_locations, constraints, N)]; int cur_line_count = 0; for (uint64_t line : lines) { cur_line_count += ((line ^ constraints) & constraint_locations) == 0; } if (cur_line_count <= 1) { res = 0; } else { res = 10 * N * lines.size(); for (int i = 0; i < N; ++i) { if ((constraint_locations >> i) & 1) { continue; } const uint64_t new_constraint_locations = constraint_locations | (1ULL << i); res = min( res, cur_line_count + // Line passes through station i. dp[get_key(new_constraint_locations, constraints | (1ULL << i), N)] + // Line does not pass through station i. dp[get_key(new_constraint_locations, constraints, N)]); } } if (constraints == 0) { break; } } if (constraint_locations == 0) { break; } } } return static_cast(dp[get_key(0, 0, N)]) / lines.size(); } int main() { while (cin.peek() == '#' || cin.peek() == '/') { string s; getline(cin, s); } int N; cin >> N; assert(N <= 64); // For bit masks to fit in an uint64_t. int M; cin >> M; vector lines; for (int i = 0; i < M; ++i) { uint64_t line = 0; int num_stations; cin >> num_stations; for (int j = 0; j < num_stations; ++j) { int station; cin >> station; assert(station >= 0); assert(station < N); uint64_t station_mask = 1ULL << station; // Duplicate station. assert((line & station_mask) == 0); line |= station_mask; } lines.push_back(line); } double res = solve(N, lines); if (res > 2 * N) { cout << "not possible" << endl; } else { cout << std::setprecision(15) << res << endl; } }