Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 21684. 【NOIP Round #2】就这

统计

题目描述

小 A 给出了三个整数 $n,m,k$ 满足 $0\le k\le m< n$,他想让小 B 构造一个长度为 $n$ 的 01 串。

小 B 说:“就这?”,然后随手写下了 $n$ 个 1 ,显然这个串是满足条件的。

小 A 不想让 1 的个数太多,于是要求这个 01 串每个长度为 $m$ 的子串至多有 $k$ 个 1

小 B 说:“就这?”,然后随手写下了 $n$ 个 0 ,显然这个串也是满足条件的。

小 A 也不想让 1 的个数太少,于是又要求这个 01 串每个长度为 $m+1$ 的子串至少有 $k$ 个 1

你说:“就这?”,然后也要随手写下一个满足小 A 给的所有条件的串。

在本题中约定 $T$ 是 $S$ 的子串当且仅当 $T$ 是由 $S$ 从头或从尾删掉若干个字符(可以不删)形成的串。

输入格式

共一行,包含三个整数,依次为 $n,m,k$。

输出格式

共一行一个长度为 $n$ 的 01 串,如果有多个串满足条件输出任意一个即可。

样例

样例输入 1

4 2 1

样例输出 1

0100

样例解释 1

0100 共有 $3$ 个长度为 $m$ 的子串,分别为 011000,它们均只包含 $\le k$ 个 1

0100 共有 $2$ 个长度为 $m+1$ 的子串,分别为 010100 ,它们均包含 $\ge k$ 个 1

0100 满足条件。

同时,不止一个串满足条件,比如 0010 也满足条件,所以输出 0010 也是正确的!

样例输入 2

5 4 4

样例输出 2

11111

数据范围

本题共有 $10$ 个测试点,每个测试点 $10$ 分。

对于所有测试点,保证 $0\le k\le m< n\le 10^5,0< m$。

对于测试点 $1,2$,保证 $n\le 20$。

对于测试点 $3,4$,保证 $n\le 100$。

对于测试点 $5,6$,保证 $n\le 1000$。

对于测试点 $7$,保证 $k=m$。

对于测试点 $8$,保证 $m=n-1$。

对于测试点 $9,10$,无特殊限制。