TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P8118
  • Problem
  • P8118天才的博弈
    Limits : Time Limit : - MS   Memory Limit : - KB  SPJ
    Judgment Tips : 1s 256MB
    Description

    $A\_Handsome\_Boy$得到了三个整数$a,b,k$,他要寻找两个二进制数$x,y$,满足:

    • $x$和$y$都由$a$个$0$和$b$个$1$组成;

    • \(x-y\)(同样由二进制表示)含有$k$个$1$;

    • $x$和$y$不含前导$0$

    Input Format

    一行,三个整数$a,b,k;(0\le a;,1\le b;,0\le k\le a+b \le 2 \times 10^5)$。

    Output Format

    若答案存在,第一行输出一个字符串“Yes”(不含双引号),第二行和第三行输出两个二进制数$x$和$y$;

    若答案不存在,直接输出"No"。

    如果有多解,输出任意一组解。

    Sample Input 1

    4 2 3

    Sample Output 1

    Yes
    101000
    100001

    Sample Input 2

    3 2 1

    Sample Output 2

    Yes
    10100
    10010

    Sample Input 3

    3 2 5

    Sample Output 3

    No

    Hint

    在第一组样例中,\(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}$, 因此$x-y$在二进制下有$3$个$1$;

    在第二组样例中,\(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}$,含有$1$个$1$;

    在第三组样例中,可以证明该情况无解。