QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
Statistics

非官方翻译,来自 Qingyu

给定 $N, K, L$,构造两个 0/1 串 $S, T$,使得:

  • $S, T$ 的长度均为 $N$。
  • $S$ 中包含恰好 $K$ 个 $1$。
  • $T$ 中包含恰好 $L$ 个 $1$。

在此基础上,你希望最小化:

  • 将 $S,T$ 任意循环移位后,0/1 串 $R_i = S_i\operatorname{and} T_i$ 中 $1$ 的个数的最大值。

即,你要最小化将两个串任意循环移位后,所有两串均为 $1$ 的位置的数量。

输入格式

输入只有一行,包含三个整数 $N, K, L$。保证 $0 \leq K,L \leq N$。

输出格式

输出的第一行包含一个整数,表示最优方案下的最小值。

接下来一行,描述你构造的串 $S$。

接下来一行,描述你构造的串 $T$。

若有多组合法的方案,你可以输出任意一组。

子任务

子任务 分值 额外限制
$1$ $5$ $1 \leq N \leq 13$
$2$ $50$ $1 \leq N \leq 5\,000$
$3$ $45$ $1 \leq N \leq 500\,000$

特别地,如果你的程序仅在第一行输出了正确的结果,但构造的方案错误,你可以获得该测试点 $20\%$ 的分数。

样例数据

样例 1 输入

6 4 3

样例 1 输出

2
011011
101010

样例 2 输入

5 2 0

样例 2 输出

0
01001
00000

样例 3 输入

10 7 6

样例 3 输出

5
1101100111
1110001101