Valleys and Hills

 CODECHEF

Chef built a binary string 

S$S$ that has exactly N$N$ hills and M$M$ valleys.

• A hill is any index 1<i<|S|$1<i<|S|$ such that both its neighbors are strictly smaller than it, i.e, Si−1<Si$S_{i-1}<S_i$ and Si+1<Si$S_{i+1}<S_i$.

• A valley is any index 1<i<|S|$1<i<|S|$ such that both its neighbors are strictly larger than it, i.e, Si−1>Si$S_{i-1}>S_i$ and Si+1>Si$S_{i+1}>S_i$.

Chef thinks that his string S$S$ is the shortest among all binary strings with N$N$ hills and M$M$ valleys. You don't quite trust his words, so to verify his claim you would like to find the shortest binary string with exactly N$N$ hills and M$M$ valleys.

If there are multiple possible binary strings of the least length satisfying the given condition, you may print any of them.

Input Format

• The first line of input will contain a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• The first and only line of each test case contains two space-separated integers N$N$ and M$M$, the required number of hills and valleys respectively.

Output Format

For each test case, output two lines.

• The first line contains the length of the binary string you constructed to satisfy the given conditions.
• The second line contains the string itself.

Constraints

• 1≤T≤2500$1\le T\le 2500$
• 1≤N≤500$1\le N\le 500$
• 1≤M≤500$1\le M\le 500$
• The sum of lengths of the answer strings across all test cases does not exceed 2⋅105$2\cdot {10}^5$

Subtasks

Subtask 1 (10 points):

• 1≤N≤50$1\le N\le 50$
• 1≤M≤50$1\le M\le 50$
• You may output any string of length not exceeding 320$320$ containing exactly N$N$ hills and M$M$ valleys: it need not be shortest by length. It is guaranteed that at least one such string with length ≤320$\le 320$ exists.

Subtask 2 (90 points):

• Original constraints
• The binary string you construct must be shortest by length.

Sample Input 1 

3
3 2
2 3
3 3

Sample Output 1 

7
0101010
7
1010101
8
01010101

Explanation

Test case 1$1$: The given string has hills at indices 2,4,6$2,4,6$ and valleys at indices 3,5$3,5$. It can be verified that there is no string of length 6$6$ or less with 3$3$ hills and 2$2$ valleys. Note that for subtask 1$1$, a binary string like 001010100$001010100$ will also be accepted as a valid output, even though it is not shortest by length.

Test case 3$3$: Apart from the given string, another possible string of length 8$8$ that has 3$3$ hills and 3$3$ valleys is 10101010$10101010$. You may print any of them.

• Tweet
• Share
• Share
• Share
• Share

Related Post