C++

Forum

 
Can anyone help me to do this Question

zyan1zyan (52)
You are given three integers a, b and . Your task is to construct a binary string s of length n=a+b such that there are exactly a zeroes, exactly b ones and exactly x positions i (1≤i<n) such that si≠si+1. It is guaranteed that the answer always exists.

Recall that binary string is a non-empty sequence of characters where each character is either 0 or 1.

Input
The first line of the input contains three integers a, b and x(1≤a,b≤100,1≤x<a+b).

Output
Print only one string s, where s is any binary string satisfying conditions described above. It is guaranteed that the answer always exists.

Examples
input
2 2 1
output
1100

input
3 3 3
output
101100

input
5 3 6
output
01010100

Note
All possible answers for the first example:

1100;
0011.
All possible answers for the second example:

110100;
101100;
110010;
100110;
011001;
001101;
010011;
001011.
closed account 1TD80pDG (101)
@tpb ?? and @lastchance ?? plz reply
closed account 1TD80pDG (101)
@zyan1zyan modify question
You are given three integers a, b and x.
closed account 1TD80pDG (101)
i solved this way but its gives TLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 


 do
    {
       
        
        int count=0;
        for(int i=0; i<a+b-1; i++)
        {
            if(str[i]!=str[i+1])
                count++;
            
        }
     
        if(count==x)
        {
           
            cout<<str<<endl;
            break;
            
        }
        
        
    }
    while(next_permutation(str.begin(),str.end()));
closed account (iT0i3TCk)
TLE on test case 9 right?
closed account 1TD80pDG (101)
@iamx yes, do you have any alternative plz suggest?
Last edited on
Repeater (3046)
Write zero if a is bigger, write one if b is bigger. If a==b, write a zero.
Then write the opposite.

01 - this is {1,1,1}

Keep going until you've got the required value for x.

01010101 - this is {4,4,7}

When you've got the required value for x, put in all the remaining characters where they won't change x:

0000000 01010101 1111 - this is {8,8,7}

0 01010101 111111111 - this is {5,13, 7}

Once you've got the string with the right x value, you can always insert as many 0 and 1 characters as you like without changing the value of x.
Last edited on
closed account (iT0i3TCk)
can you show it for even x?
Repeater (3046)
a=2, b=1, x=2

a is bigger, so write a zero:
0

Now write a 1:
01

Now write a 0:
010 - this is {2,1,2}
closed account 1TD80pDG (101)
@Repeater can you find the error in my code it gives the wrong answer on test case 7


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 

#include <bits/stdc++.h>

using namespace std;
int main()
{
   int a,b,x;
    cin>>a>>b>>x;
    
    string str="";
    for(int i=0; i<a; i++)
    {  if(i<a)
        str=str+"0";
   
    }
    
    for(int i=0; i<b; i++)
        str=str+"1";
    
 
    
    string str1="";
    int count_0=0,count_1=0;
    for(int i=0; i<x; i++)
    {   
        if(i%2==0)
        {  str1=str1+"0";
         count_0++;
        }
        else
        {   str1=str1+"1";
         count_1++;
        }
        
    }
    
   
    if(char(str1[x-1])=='0')
    {   str1=str1+"1";
     count_1++;
    }
    else
    {      str1=str1+"0";
    count_0++;
    }
    
 
    int rem_0=a-count_0;
    int rem_1=b-count_1;
 
    
    string s1="";
    for(int i=0; i<rem_0; i++)
        s1=s1+"0";
    
     string s2="";
    for(int i=0; i<rem_1; i++)
        s2=s2+"1";
    
  
     str1.insert(1, s2);
    str1=s1+str1;
   
    
   
    
    
    
    cout<<str1;
    
    
    
}
Last edited on
closed account 1TD80pDG (101)
solved it. thanks @Repeater
icy1 (596)
yep, I basically had same strategy as Repeater. Do the "flips" first. My eventual output began with 0.

1. check if "flips" is odd
2. populate stream (or string buffer) with alternating 1 and 0 while decrementing flips and appropriately decrementing ones and zeroes
3a. if odd flips, append remaining 1's to stream. Output remaining 0's.
3b. else Output remaining 0's and Output remaining 1's.
4. Output stream.

Codechef or Hackerrank? having trouble googling to try my solution ;D
Last edited on
icy1 (596)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main() 
{
    int zeroes, ones, flips;
#if 1
    istringstream iss("3 3 3\n");
    iss >> zeroes >> ones >> flips;
#else
    cin >> zeroes >> ones >> flips;
#endif
    cout << "zeroes: "<<zeroes << '\n';
    cout << "ones: "<<ones << '\n';
    cout << "flips: "<<flips << '\n';
    cout << endl;

    ostringstream oss;
    int k = 1;
    bool oddflips = flips & 1;
    while (flips--)
    {
        oss << k;
        k ? ones-- : zeroes--;
        k = !k;
    }

    cout << string(zeroes, '0');
    if (oddflips)
    {
        cout << oss.str() << string(ones, '1');      
    }
    else
    {
        cout << string(ones, '1') << oss.str();
    }
    cout << endl;

    return 0;

}


https://repl.it/@icy_1/RapidWrongFields

Edit: after some more thought, I probably don't need to care about odd or even -- could just forget about appending the 1's at the end and instead just insert immediately after the remaining 0's every time.

can i haz problem link pl0x? those sites seem to not have a search function...
Last edited on
Repeater (3046)
Indeed. Just make a string of all the zeros, or all the ones, whichever you need more of, and then just start inserting the opposite between them until you've got all the flips you need. Any leftover zeros or ones can be easily inserted where they don't affect the flips.
Last edited on
Topic archived. No new replies allowed.