Skip to content

Latest commit

 

History

History
92 lines (62 loc) · 2.99 KB

0401c.md

File metadata and controls

92 lines (62 loc) · 2.99 KB
Raw

题目地址(C. Team)

https://codeforces.com/problemset/problem/401/C

题目描述

Now it's time of Olympiads. Vanya and Egor decided to make his own team to take part in a programming Olympiad. They've been best friends ever since primary school and hopefully, that can somehow help them in teamwork.

For each team Olympiad, Vanya takes his play cards with numbers. He takes only the cards containing numbers 1 and 0. The boys are very superstitious. They think that they can do well at the Olympiad if they begin with laying all the cards in a row so that:

there wouldn't be a pair of any side-adjacent cards with zeroes in a row;
there wouldn't be a group of three consecutive cards containing numbers one.
Today Vanya brought n cards with zeroes and m cards with numbers one. The number of cards was so much that the friends do not know how to put all those cards in the described way. Help them find the required arrangement of the cards or else tell the guys that it is impossible to arrange cards in such a way.

Input
The first line contains two integers: n (1 ≤ n ≤ 106) — the number of cards containing number 0; m (1 ≤ m ≤ 106) — the number of cards containing number 1.

Output
In a single line print the required sequence of zeroes and ones without any spaces. If such sequence is impossible to obtain, print -1.

Examples
inputCopy
1 2
outputCopy
101
inputCopy
4 8
outputCopy
110110110101
inputCopy
4 10
outputCopy
11011011011011
inputCopy
1 5
outputCopy
-1

前置知识

  • 构造

公司

  • 暂无

思路

这是一道构造题，需要我们构建出满足条件的字符串。

不妨从特殊情况推导。

  • 如果 0 的数目和 1 的数目一样，那么此时我们可以安排为 10 缴交错，从而构造一个合法序列。

  • 如果 0 的数目比 1 的数目多 1， 我们可以安排为 010101.. 而不是 101010...，这样我们就可以在后面补多余的一个 0 从而构造合法序列。

  • 如果 0 的数目比 1 的数目多 2， 则无论如何都不合法。 多 3，多 4 都是类似的，均不合法。这是因为不管是 010101... 这种，还是 10101010... 这种，都会因为 0 还有没有安排的，从而不得不有两个相邻 0 的情况。

由于 1 可以连续两个，不可以连续三个 我们可以将两个 1 看成一个 0，从而将问题转化为上面的问题。思路是类似的，不再赘述。

关键点

代码

  • 语言支持：Python3

Python3 Code:

n, m = map(int, input().split())
# 注意： cf 中不能有中文注释。因此你要提交的话，请把包含中文的注释去掉
if n > m + 1 or m > 2 * n + 2:
    print(-1)
elif n >= m:
    # 0 多，把 0 放两边
    print("01" * m + "0" * int((n == m + 1)))
else:
    # 1 多，把 1 放两边
    print(("10" * n + "1").replace("1", "11", m - n - 1))  # 由于 1 可以连续放两个，如果可能的话（1 还足够）那就贪心地放两个

复杂度分析

  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(1)$