// Same as raphael_v3, except that we on purpose add 9e-5 to make sure // that the judge accepts answers within 1e-4 of the correct answer. #include #include #include #include #include #include #include #include #include #include using namespace std; using Memo = vector>; int64_t dp_no_div(uint64_t constraint_locations, uint64_t constraints, int N, const vector &lines, Memo &memo) { int cur_line_count = 0; for (uint64_t line : lines) { cur_line_count += ((line ^ constraints) & constraint_locations) == 0; } if (cur_line_count <= 1) return 0; // Can decide without any additional question. auto &memo_with_locations = memo[constraint_locations]; auto it = memo_with_locations.find(constraints); if (it != memo_with_locations.end()) return it->second; int64_t res = 10 * N * lines.size(); 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); // Ask question about station i. res = min(res, cur_line_count + // Line passes through station i. dp_no_div(new_constraint_locations, constraints | (1ULL << i), N, lines, memo) + // Line does not pass through station i. dp_no_div(new_constraint_locations, constraints, N, lines, memo)); } return (memo_with_locations[constraints] = res); } 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; int sum_stations = 0; 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; sum_stations += 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 t = time(nullptr); t = time(nullptr); Memo memo; memo.resize(1ULL << N); double res = static_cast(dp_no_div(0, 0, N, lines, memo)) / M; // cout << "DP time: " << time(nullptr) - t << endl; double TARGET_TOLERANCE = 1e-4; TARGET_TOLERANCE *= 0.99; if (res > 2 * N) { cout << "not possible" << endl; } else { cout << res + (sum_stations % 2 == 0 ? TARGET_TOLERANCE : -TARGET_TOLERANCE) << endl; } }