BAN BAN (Codeforces 1747B)
Tags: Others, constructive algorithms

You are given an integer $$$n$$$.Let's define $$$s(n)$$$ as the string "BAN" concatenated $$$n$$$ times. For example, $$$s(1)$$$ = "BAN", $$$s(3)$$$ = "BANBANBAN". Note that the length of the string $$$s(n)$$$ is equal to $$$3n$$$.Consider $$$s(n)$$$. You can perform the following operation on $$$s(n)$$$ any number of times (possibly zero): Select any two distinct indices $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq 3n, i \ne j)$$$. Then, swap $$$s(n)_i$$$ and $$$s(n)_j$$$. You want the string "BAN" to not appear in $$$s(n)$$$ as a subsequence. What's the smallest number of operations you have to do to achieve this? Also, find one such shortest sequence of operations.A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters.

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 100)$$$  — the number of test cases. The description of the test cases follows.The only line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 100)$$$.

Output: For each test case, in the first line output $$$m$$$ ($$$0 \le m \le 10^5$$$) — the minimum number of operations required. It's guaranteed that the objective is always achievable in at most $$$10^5$$$ operations under the constraints of the problem. Then, output $$$m$$$ lines. The $$$k$$$-th of these lines should contain two integers $$$i_k$$$, $$$j_k$$$ $$$(1\leq i_k, j_k \leq 3n, i_k \ne j_k)$$$ denoting that you want to swap characters at indices $$$i_k$$$ and $$$j_k$$$ at the $$$k$$$-th operation. After all $$$m$$$ operations, "BAN" must not appear in $$$s(n)$$$ as a subsequence. If there are multiple possible answers, output any.

Note: In the first testcase, $$$s(1) = $$$ "BAN", we can swap $$$s(1)_1$$$ and $$$s(1)_2$$$, converting $$$s(1)$$$ to "ABN", which does not contain "BAN" as a subsequence.In the second testcase, $$$s(2) = $$$ "BANBAN", we can swap $$$s(2)_2$$$ and $$$s(2)_6$$$, converting $$$s(2)$$$ to "BNNBAA", which does not contain "BAN" as a subsequence.

Sample Inputs:
2
1
2

Sample Outputs:
1
1 2
1
2 6

Solution (Python):
for n in [*map(int, open(0))][1:]:
    print(n + 1 >> 1)
    i = 1
    j = n * 3
    while i < j:
        print(i, j)
        i += 3
        j -= 3

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    s = 'BAN' * n
    l = 0
    r = len(s) - 1
    sett = []
    while l <= r:
        if s[r] == 'N' and s[l] != 'N':
            sett.append([l + 1, r + 1])
            r -= 3
            l += 3
        else:
            l += 1
    print(len(sett))
    for i in sett:
        print(*i)

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    s = 'BAN' * n
    l = 0
    r = len(s) - 1
    sett = []
    while l <= r:
        if s[r] == 'N' and s[l] != 'N':
            sett.append([l + 1, r + 1])
            r -= 3
            l += 3
        else:
            l += 1
    print(len(sett))
    for i in sett:
        print(*i)