// Solved by Gemini3.0 // 問題文を与えて全部任せました。インタラクティブのジャッジも書いてもらいました。 #include #include #include #include #include #include using namespace std; // Function to calculate Hit and Blow pair get_hit_blow(const string& s, const string& q) { int h = 0; int b = 0; // s and q are guaranteed to be distinct digit strings of length 5 // But let's be generic for (int i = 0; i < 5; ++i) { if (s[i] == q[i]) { h++; } } for (int i = 0; i < 5; ++i) { for (int j = 0; j < 5; ++j) { if (i == j) continue; if (s[i] == q[j]) { b++; } } } return {h, b}; } bool has_distinct_digits(const string& s) { int mask = 0; for (char c : s) { int d = c - '0'; if ((mask >> d) & 1) return false; mask |= (1 << d); } return true; } int main() { // Optimize I/O operations ios_base::sync_with_stdio(false); // cin.tie(NULL); // Do not untie, we need flush behavior? // Actually interactive problems usually require flush. // cin.tie(NULL) prevents automatic flush of cout before cin. // We strictly manually flush or use endl. vector candidates; candidates.reserve(30240); for (int i = 0; i < 100000; ++i) { string s = to_string(i); while (s.length() < 5) s = "0" + s; if (has_distinct_digits(s)) { candidates.push_back(s); } } set found_strings; // We need to find 30 strings. while (found_strings.size() < 30) { // Pick a query // We pick the first candidate that is not already found. // Actually, we can just remove candidates as we go. // But filtering creates a new vector anyway. string q; if (candidates.empty()) { // Should not happen if logic is correct and 30 strings exist break; } q = candidates[0]; // Output query cout << q << endl; // Read response vector> response(30); int cnt_5_0 = 0; map, int> response_counts; for (int i = 0; i < 30; ++i) { cin >> response[i].first >> response[i].second; if (response[i] == make_pair(5, 0)) { cnt_5_0++; } response_counts[response[i]]++; } // Check if we found new strings // The number of (5, 0) tells us exactly how many found strings are there. // If q was not in found_strings, and now we have more (5,0)s, q is found. // Wait, 'cnt_5_0' is the TOTAL number of identified strings. // Check if q is a newly found string bool q_is_found = false; if (cnt_5_0 > (int)found_strings.size()) { // Since we only query one string q at a time, // the count can increase by at most 1 (if q is a new hidden string). // It matches q. found_strings.insert(q); q_is_found = true; } if (found_strings.size() == 30) { break; } // Prepare the multiset of responses for the UNKNOWN candidates. // We remove 'cnt_5_0' counts of (5, 0) from the response_counts. // Because those correspond to the found strings (including q if it was found). if (response_counts.count({5, 0})) { response_counts[{5, 0}] -= cnt_5_0; if (response_counts[{5, 0}] <= 0) { response_counts.erase({5, 0}); } } // Filter candidates vector next_candidates; next_candidates.reserve(candidates.size()); for (const string& c : candidates) { // If c is already found, we don't need to keep it in candidates // (Unless we want to be explicit, but it's better to remove to shrink search space) if (found_strings.count(c)) continue; // If c == q and q was NOT found, then c is definitely not a hidden string. // (If q was found, we already skipped it above). if (c == q) continue; pair hb = get_hit_blow(c, q); // Check if hb is in the remaining response counts if (response_counts.count(hb)) { next_candidates.push_back(c); } } candidates = next_candidates; } return 0; }