codeforces 704(div.2)D. Genius's Gambit

时间：2021-03-03 21:42:22 阅读：36 评论：0 收藏：0 [点我收藏+]

You are given three integers $a$ , $b$ , $k$ .

Find two binary integers $x$ and $y$ ( $x \geq y$ ) such that

both $x$ and $y$ consist of $a$ zeroes and $b$ ones;
$x - y$ (also written in binary form) has exactly $k$ ones.

You are not allowed to use leading zeros for

x

and

y

Input

The only line contains three integers $a$ , $b$ , and $k$ ( $0 \leq a$ ; $1 \leq b$ ; $0 \leq k \leq a + b \leq 2 \cdot 10^{5}$ ) — the number of zeroes, ones, and the number of ones in the result.

Output

If it‘s possible to find two suitable integers, print "Yes" followed by $x$ and $y$ in base-2.

Otherwise print "No".

If there are multiple possible answers, print any of them.

Examples

Input

Copy

4 2 3

Output

Copy

Yes
101000
100001

Input

Copy

3 2 1

Output

Copy

Yes
10100
10010

Input

Copy

3 2 5

Output

Copy

No

Note

In the first example, $x = 101000_{2} = 2^{5} + 2^{3} = 40_{10}$ , $y = 100001_{2} = 2^{5} + 2^{0} = 33_{10}$ , $40_{10} - 33_{10} = 7_{10} = 2^{2} + 2^{1} + 2^{0} = 111_{2}$ . Hence $x - y$ has $3$ ones in base-2.

In the second example, $x = 10100_{2} = 2^{4} + 2^{2} = 20_{10}$ , $y = 10010_{2} = 2^{4} + 2^{1} = 18$ , $x - y = 20 - 18 = 2_{10} = 10_{2}$ . This is precisely one 1.

In the third example, one may show, that it‘s impossible to find an answer.

题意：balabala
题解：思维题，通过构造能够得到最多a+b-2个1，
我们通过先想最简单的做法不难得到当b=2时显而易见这种方式能够得到最多的1：
110000000
100000001
并且我们可以移动第二位的数对(1,0)来得到最多a+b-2个1，是以这种方式移动的：
100010000
100000001(相减得到4个1)
我们再考虑b>=3的情况来看：
例如：
111100000
101100001
显而易见，我们可以移动第二位的数对(1,0)来得到最多不超过a+b-2个1，如果还不明白，这是因为上面相减依然可以写成：
110000000
100000001
很熟悉吧，就变成了b=2时的简单情况，于是我们就会处理了！
(代码有点乱)
$Coding:$

/*************************************************************************
    > File Name: D.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2021年03月03日 星期三 19时38分22秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
using namespace std;
int a,b,k;
void solve(){
	scanf("%d%d%d",&a,&b,&k);
	int mx = a + b - 2 ;
	int n = a + b ;
	if(!a){
		if(k)printf("No");
		else {
			puts("Yes");
			rep(i,1,2){
				rep(j,1,n)printf("1");puts("");
			}
		}return ;
	}
	if(k>mx)puts("No");
	else {
		if(b == 1){
			if(k)puts("No");
			else {
				puts("Yes");
				rep(j,1,2){
				printf("1");
				rep(i,1,a)printf("0");
				puts("");
				}
			}
		}
		else if(b == 2){
			puts("Yes");
			printf("1");
			int now = 2;
			rep(i,2,n-k-1)printf("0");
			printf("1");
			rep(i,n-k,n-1)printf("0");
			puts("");
			printf("1");
			rep(i,2,n-1)printf("0");
			puts("1");
		}
		else {
			puts("Yes");
			rep(i,1,n){
				if(i<=b-1||i==n-k||(n-k<=b-1&&i==b))printf("1");
				else printf("0");
			}
			puts("");
			int cnt = 0;
			rep(i,1,n-1){
				if(i==n-k)printf("0");
				else if(cnt<b-1)printf("1"),cnt++;
				else printf("0");
			}
			puts("1");
		}
	}
}
signed main(){
	solve();
	return 0;
}

codeforces 704(div.2)D. Genius's Gambit

原文：https://www.cnblogs.com/violentbear/p/14476730.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)