QOJ.ac
QOJ
Time Limit:
2 s
Memory Limit:
512 MB
Total points:
100
Izborne Pripreme
B. Maliand
非官方翻译,来自 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