#include <string>
#include <vector>
#include <numeric> // Not strictly needed but good practice for potential future use
#include <stdexcept> // For potential error handling if needed
// Forward declaration for the grader's function, assuming it's linked externally
// or provided in a header file (e.g., "combo.h")
// If using a specific contest environment, include the provided header.
// #include "combo.h"
extern int press(std::string p);
// Function to guess the secret sequence
std::string guess_sequence(int N) {
std::string guessed_S = ""; // The string we are building
char first_char = 0; // To store the first character once found
std::vector<char> all_chars = {'A', 'B', 'X', 'Y'};
// --- Step 1: Determine the first character S[0] ---
// We can determine the first character by pressing single characters.
// If press("A") returns 1, the first character is 'A'.
// Otherwise, try "B", then "X". If none return 1, it must be "Y".
// This takes at most 3 calls to press().
if (N == 0) {
return ""; // Handle the edge case of N=0, though constraints likely guarantee N>=1
}
// Try A
if (press("A") == 1) {
guessed_S = "A";
} else if (press("B") == 1) { // Try B if A failed
guessed_S = "B";
} else { // If A and B failed, try X
// We can optimize slightly: if press("X") == 1, it's X.
// If press("X") == 0, it must be Y. We don't need press("Y").
if (press("X") == 1) {
guessed_S = "X";
} else {
guessed_S = "Y";
}
}
// Store the first character, knowing it won't repeat later.
first_char = guessed_S[0];
// If N is 1, we are already done.
if (N == 1) {
return guessed_S;
}
// --- Step 2: Determine the remaining characters S[1] to S[N-1] ---
// We will determine the characters one by one.
// Let the currently known prefix be `guessed_S`. Its length is `k`.
// We want to find the next character `S[k]`.
// We know `S[k]` cannot be `first_char`.
// So, there are 3 possible candidates for `S[k]`. Let them be `c1, c2, c3`.
// Optimized strategy:
// Press `guessed_S + c1 + guessed_S + c2`.
// - If result is `k`, it means neither `guessed_S + c1` nor `guessed_S + c2`
// is a prefix of S found in the pressed string. This implies the
// longest prefix found is still `guessed_S` (length k). Since we know the
// next character must be one of c1, c2, c3, and it's not c1 or c2,
// it *must* be c3. (1 press call)
// - If result is `k+1`, it means *either* `guessed_S + c1` *or* `guessed_S + c2`
// is the correct next prefix S[0...k]. We need one more call to distinguish.
// Press `guessed_S + c1`.
// - If result is `k+1`, then `S[k]` is `c1`. (2 press calls total for this step)
// - If result is `k`, then `S[k]` must be `c2`. (2 press calls total for this step)
// This determines each subsequent character in at most 2 calls.
while (guessed_S.length() < N) {
int k = guessed_S.length();
char next_char = 0; // To store the determined next character
// Identify the three candidate characters (all except first_char)
std::vector<char> candidates;
for (char c : all_chars) {
if (c != first_char) {
candidates.push_back(c);
}
}
// `candidates` now holds the 3 possible next characters, let's call them c1, c2, c3.
char c1 = candidates[0];
char c2 = candidates[1];
char c3 = candidates[2];
// First query combining two candidates
int r1 = press(guessed_S + c1 + guessed_S + c2);
if (r1 == k) {
// Neither c1 nor c2 worked when appended, so the next char must be c3
next_char = c3;
} else { // r1 == k + 1, meaning either c1 or c2 is the next character
// Second query to distinguish between c1 and c2
int r2 = press(guessed_S + c1);
if (r2 == k + 1) {
// Appending c1 resulted in the longer prefix match, so c1 is next
next_char = c1;
} else { // r2 == k
// Appending c1 didn't extend the match, so c2 must be next
next_char = c2;
}
}
// Append the determined character to our result
guessed_S += next_char;
}
// After the loop, guessed_S should have length N and be the correct sequence.
return guessed_S;
}
// --- Explanation ---
//
// 1. **Finding S[0]:** The first character is found by testing 'A', 'B', and 'X' individually using `press`. If `press(C)` returns 1, then `S[0]` is `C`. If none of 'A', 'B', 'X' return 1, `S[0]` must be 'Y'. This takes a maximum of 3 `press` calls.
// 2. **Finding S[k] for k > 0:**
// * We know `S[k]` cannot be `S[0]`. This leaves 3 possibilities.
// * Let the current known prefix be `P = guessed_S` (length `k`).
// * Let the 3 candidates be `c1`, `c2`, `c3`.
// * We use a 2-stage query process:
// * **Query 1:** `press(P + c1 + P + c2)`. This string contains potential prefixes `P+c1` and `P+c2`.
// * **Analysis 1:**
// * If `press` returns `k`: The longest prefix of `S` found is still `P`. This means neither `P+c1` nor `P+c2` is the *next* prefix `S[0...k]`. Therefore, the next character `S[k]` *must* be `c3`. We found `S[k]` in 1 call.
// * If `press` returns `k+1`: The longest prefix found is length `k+1`. This means either `P+c1` or `P+c2` (or both, if they are identical which isn't possible here) matches `S[0...k]`. We need to know *which* one is correct.
// * **Query 2 (only if Query 1 returned k+1):** `press(P + c1)`.
// * **Analysis 2:**
// * If `press` returns `k+1`: The prefix `P+c1` matches `S[0...k]`. So, `S[k]` is `c1`. We found `S[k]` in 2 calls total for this step.
// * If `press` returns `k`: The prefix `P+c1` does *not* match `S[0...k]`. Since we knew from Query 1 that either `c1` or `c2` was correct, `S[k]` must be `c2`. We found `S[k]` in 2 calls total for this step.
// 3. **Complexity:**
// * Finding `S[0]` takes at most 3 calls.
// * Finding each subsequent character `S[1]` to `S[N-1]` takes at most 2 calls.
// * Total calls: Max `3 + 2 * (N - 1)`.
// * For `N = 2000`, max calls = `3 + 2 * 1999 = 3 + 3998 = 4001`.
// * This is well within the 8000 limit and should achieve the highest score tier (related to `2N + C` calls).
// 4. **Constraints:** The pressed string length in `press(P + c1 + P + c2)` is `k + 1 + k + 1 = 2k + 2`. Since max `k` is `N-1`, the max length is `2(N-1) + 2 = 2N`. This is within the `4N` limit. The length in `press(P + c1)` is `k+1`, maximum `N`, also within limits.
