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<n)
such that si≠si+1. It is guaranteed that the answer always exists.
For example, for the string “01010” there are four indices i such that1≤i<n and si≠si+1 ``(i=1,2,3,4).
For the string “111001” there are two such indices i(i=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).
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.
这题借鉴了一下同学的思路 结果我先a了 他还没a
就是给一定数量的0或1 然后要求构造出01串满足相邻不同的数量等于所给的x
首先可以看出
01—1个不同
0101—3个不同
010101—5个不同
所以我们先判断x是奇是偶,如果是偶数,先减1变成奇数
所以有x个不同 就有x/2 个01串
然后现在串左边就是0,右边就是1,再判断剩下的情况,
如果x本来就是奇数的,这时候已经构造完成了,剩下的就是把剩下的0放左边 1放右边
(这里今天又get到了c++ string的用法 原来也可以用+来连接字符串)
然后就是x本来是偶数的情况了,又分为三种情况
0 1 都剩有:
因为还缺一个不同,所以先把所有0放左边,然后再把所有1也放左边,那这样又产生了一个01串
只剩下0:
0全部放左边
只剩下1:
1全部放右边
代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
const int MAXN=205;
int main(void){
int a,b,x;
string res="";
scanf("%d%d%d",&a,&b,&x);
int f=0;
if(x%2==0){
x--;
f=1;
}
int t=(x+1)/2;
while(t--){
res+="01";
a--;
b--;
}
if(f){
if(a && b){
while(a--){
res="0"+res;
}
while(b--){
res="1"+res;
}
}
else if(a){
while(a--){
res+="0";
}
}
else if(b){
while(b--){
res="1"+res;
}
}
}
else{
while(a--){
res="0"+res;
}
while(b--){
res+="1";
}
}
cout << res << endl;
return 0;
}