## Intuition The problem requires us to transform the string `s(n) = "BAN" * n` such that "BAN" does not appear as a subsequence. The key insight is that we can achieve this by disrupting the order of "B", "A", and "N" in each "BAN" segment. By swapping characters within the string, we can ensure that "BAN" cannot be formed as a subsequence. ## Approach 1. **Understanding the Problem**: We need to prevent "BAN" from appearing as a subsequence in the string `s(n)`. This can be achieved by rearranging the characters in each "BAN" segment. 2. **Strategy**: For each "BAN" segment in `s(n)`, we can swap the positions of "B" and "A" or "A" and "N" to disrupt the order. This ensures that "BAN" cannot be formed as a subsequence. 3. **Operations**: - For each "BAN" segment, swap the first and the last character of the segment. This changes "BAN" to "NAB", which does not contain "BAN" as a subsequence. - Specifically, for the `i-th` "BAN" segment (1-based index), swap the characters at positions `3*i - 2` and `3*i`. 4. **Implementation**: For each test case, compute the number of operations and the specific swaps needed. Output the results accordingly. ## Complexity - **Time Complexity**: O(n) per test case, where n is the number of "BAN" segments. This is because we perform a constant number of operations for each segment. - **Space Complexity**: O(1) additional space, as we only store a fixed number of variables. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; // Number of operations needed cout << n << '\n'; // For each "BAN" segment, swap the first and last character for (int i = 1; i <= n; ++i) { int left = 3 * i - 2; // position of 'B' in the i-th "BAN" int right = 3 * i; // position of 'N' in the i-th "BAN" cout << left << ' ' << right << '\n'; } } return 0; } ``` This solution reads the number of test cases and for each test case, it computes the required swaps to ensure "BAN" does not appear as a subsequence in `s(n)`. Each swap is printed as specified in the problem statement. The approach is efficient and straightforward, leveraging the repetitive structure of the problem.

BAN BAN

Problem Details