时间限制:7000ms
单点时限:1000ms
内存限制:256MB
描述
给定两个整数n和m,求是否存在恰好包含n个0和m个1的01串S,使得S中不存在子串"001"和"11"。
如果存在符合条件的01串则输出字典序最小的S,否则输出NO。
输入
一行两个整数,表示n和m。(0<=n,m<=100000,0<n+m)
输出
一行一个字符串,为字典序最小的S或者NO。
- 样例输入
2 3
- 样例输出
10101
由于不能存在001和11,故只能10101交叉。故任意两个1之间必定需要一个0,故1的数目不能大于0的数目加1.又由于需要字典树最小的,故在前提满足的情况下把一个0放到第一位,然后全补后串后面。于是需要特判能否在第一位放一个0.
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib> using namespace std; int n, m; int main()
{
//freopen("test.txt", "r", stdin);
int num0, num1;
while (scanf("%d%d", &n, &m) != EOF)
{
if (m > n+1)
{
printf("NO\n");
continue;
}
num0 = n - m + 1;
if (m == 0)
num0--;
num1 = m;
if (num0 > 0)
{
printf("0");
num0--;
}
for (int i = 0; i < num1; ++i)
{
if (i == 0)
printf("1");
else
printf("01");
}
for (int i = 0; i < num0; ++i)
printf("0");
printf("\n");
}
return 0;
}