// Greedy (which is wrong). This should not pass. #include #include #include #include #include #include #include #include #include #include using namespace std; int count_lines(uint64_t constraint_locations, uint64_t constraints, const vector &lines) { int count = 0; for (uint64_t line : lines) { count += ((line ^ constraints) & constraint_locations) == 0; } return count; } int64_t greedy(uint64_t constraint_locations, uint64_t constraints, const vector &lines, int N) { const int cur_line_count = count_lines(constraint_locations, constraints, lines); if (cur_line_count <= 1) return 0; // Can decide without any additional question. if (constraint_locations == (1ULL << N) - 1) { return 1e9; } int count_no_best_split = -1; int station_best_split = -1; for (int i = 0; i < N; ++i) { if ((constraint_locations >> i) & 1) { // There is already a constraint for station i. continue; } const uint64_t new_constraint_locations = constraint_locations | (1ULL << i); const int count_no = count_lines(new_constraint_locations, constraints, lines); if (abs(2 * count_no - cur_line_count) < abs(2 * count_no_best_split - cur_line_count)) { count_no_best_split = count_no; station_best_split = i; } } return cur_line_count + greedy(constraint_locations | (1ULL << station_best_split), constraints, lines, N) + greedy(constraint_locations | (1ULL << station_best_split), constraints | (1ULL << station_best_split), lines, N); } 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 = static_cast(greedy(0, 0, lines, N)) / M; if (res > 2 * N) { cout << "not possible" << endl; } else { cout << std::setprecision(15) << res << endl; } }