Valleys and Hills Solution | DEC LONG CHALLENGE | Codechef

Codechef

Chef built a binary string SS that has exactly NN hills and MM valleys.

  • hill is any index 1<i<|S|1<i<|S| such that both its neighbors are strictly smaller than it, i.e, Si−1<SiSi−1<Si and Si+1<SiSi+1<Si.
  • valley is any index 1<i<|S|1<i<|S| such that both its neighbors are strictly larger than it, i.e, Si−1>SiSi−1>Si and Si+1>SiSi+1>Si.

Chef thinks that his string SS is the shortest among all binary strings with NN hills and MM valleys. You don’t quite trust his words, so to verify his claim you would like to find the shortest binary string with exactly NN hills and MM 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 TT, denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains two space-separated integers NN and MM, 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≤25001≤T≤2500
  • 1≤N≤5001≤N≤500
  • 1≤M≤5001≤M≤500
  • The sum of lengths of the answer strings across all test cases does not exceed 2⋅1052⋅105

Subtasks

Subtask 1 (10 points):

  • 1≤N≤501≤N≤50
  • 1≤M≤501≤M≤50
  • You may output any string of length not exceeding 320320 containing exactly NN hills and MM valleys: it need not be shortest by length. It is guaranteed that at least one such string with length ≤320≤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 11: The given string has hills at indices 2,4,62,4,6 and valleys at indices 3,53,5. It can be verified that there is no string of length 66 or less with 33 hills and 22 valleys. Note that for subtask 11, a binary string like 001010100001010100 will also be accepted as a valid output, even though it is not shortest by length.

Test case 33: Apart from the given string, another possible string of length 88 that has 33 hills and 33 valleys is 1010101010101010. You may print any of them.

SOLUTION

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n, m;
        cin>>n>>m;
        string s="";
        if(n  > m){
            while(n > 0 && m > 0)
            {
                s = s + "01";
                n--;
                m--;
            }
            while(n!=0){
                s = s + "010";
                n--;
            }
        }
        else if( n < m){
            while(n > 0 && m > 0)
            {
                s = s + "10";
                n--;
                m--;
            }
            while(m!=0){
                s = s + "101";
                m--;
            }
        }
        else if(n==m)
        {
            while(n+1 > 0)
            {
                s = s + "01";
                n--;
            }
        }
        cout<<s.size()<<endl;
        cout<<s<<endl;
    }
    
    return 0;
}

Refer and Earn Rs. 1200 per referral on Upstox

Click here to know more

Read More Post Here

Leave a Comment

Your email address will not be published. Required fields are marked *

x