Algorithm

B. Binary String Constructing
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1003/problem/B
input
standard input
output
standard output

You are given three integers a�, b� and x�. 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� indices i� (where 1≤i<n1≤�<�) such that si≠si+1��≠��+1. It is guaranteed that the answer always exists.

For example, for the string "01010" there are four indices i� such that 1≤i<n1≤�<� and si≠si+1��≠��+1 (i=1,2,3,4�=1,2,3,4). For the string "111001" there are two such indices i� (i=3,5�=3,5).

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)1≤�,�≤100,1≤�<�+�).

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
Copy
2 2 1
output
Copy
1100
input
Copy
3 3 3
output
Copy
101100
input
Copy
5 3 6
output
Copy
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.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int main() {
  int a, b, x;
  cin >> a >> b >> x;

  string s;
  if(a > b)
    s = "0", --a;
  else
    s = "1", --b;

  for(int i = 0; i < x; ++i) {
    if(b > 0 && s.back() == '0')
      --b, s += '1';
    else if(a > 0)
      --a, s += '0';
  }

  for(int i = 0; i < s.length(); ++i) {
    cout << s[i];
    if(a > 0 && s[i] == '0')
      while(a-- != 0)
        cout << '0';
    if(b > 0 && s[i] == '1')
      while(b-- != 0)
        cout << '1';
  }
  cout << endl;

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2 2 1

Output

x
–
+
cmd
1100
Advertisements

Demonstration

Codeforces Solution-B. Binary String Constructing-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+