407868: GYM102911 D Dancing Queen

As their act for their school's variety show, Alice and Bob are going to perform their own remix of the classic disco song Dancing Queen! Aside from the chorus, their remix has $$$N$$$ different verses to be sung by the two of them.

The verses are labeled $$$1, 2, 3, \dots, N$$$, in sequence. Each verse sung involves more and more fabulous outfits, choreography, pyrotechnics, disco lights, etc. Let's say that the fabulousness of the $$$k$$$th verse is exactly equal to $$$k$$$. Some of these verses will be performed by Alice, and the others will be performed by Bob. So that one does not overshadow the other, they wish to ensure that the total fabulousness of their verses is as fairly divided as possible.

Formally, let $$$A$$$ be the sum of the fabulousness of verses given to Alice, and let $$$B$$$ be the sum of the fabulousness of verses given to Bob. Find any way to distribute the verses between the two of them such that $$$|A-B|$$$ is minimal.

Input consists of a single line containing a single positive integer $$$N$$$.

First, output a line containing a single integer, the minimal value of $$$|A-B|$$$.

Then, output a line containing a string of $$$N$$$ characters, where the $$$k$$$th of these characters is A if the $$$k$$$th verse goes to Alice, and B if it goes to Bob. If there are multiple solutions, output any of them.

Subtask 1: (40 pts):

$$$1 \leq N \leq 15$$$

Subtask 2: (20 pts):

$$$1 \leq N \leq 100$$$

Subtask 3: (15 pts):

$$$1 \leq N \leq 1000$$$

Subtask 4: (25 pts):

$$$1 \leq N \leq 2\cdot 10^5$$$

3

0
AAB

10

1
BAAAAABABB

If there are $$$3$$$ verses, then we can make $$$|A-B|=0$$$ if we give Alice verses $$$1$$$ and $$$2$$$ while Bob gets verse $$$3$$$.

If there are $$$10$$$ verses, then we can prove that $$$|A-B|=1$$$ is the lowest we can make it. In the example, Alice gets verses $$$2, 3, 4, 5, 6$$$, and $$$8$$$, for a total fabulousness of $$$28$$$, while Bob gets verses $$$1, 7, 9$$$, and $$$10$$$, for a total fabulousness of $$$27$$$.

In both cases, it is equally valid if we gave Alice the verses we had given to Bob, and vice versa.