Jumbled String （Kattis - jumbledstring）(思维题)

Problem

Recall that a subsequence of a string is any string obtained by removing some subset of characters from the string, for instance “string”, “sing”, “i” and “sg” are all subsequences of “string”. If the same subsequence can be obtained in exactly t different ways, by removing different subsets of characters, we say that the subsequence occurs t times.

Jingfei wants to create a nonempty bit string that has the following properties:

the subsequence 00 occurs a times,

the subsequence 01 occurs b times,
the subsequence 10 occurs c times, and
the subsequence 11 occurs d times.

However, Jingfei does not know how to create such a string – or whether it is even possible. Could you help her?

Input

The input consists of a single line with four integers a, b, c, and d (0≤a,b,c,d≤1e9).

Output

Output a bit string that satisfies the given requirements. If there are several solutions, output any one of them. If there are no solutions, output “impossible”.

Sample Input 1	Sample Output 1
3 4 2 1	01001

Sample Input 2	Sample Output 2
5 0 0 5	impossible

题解：不需要考虑00、11，根据a个00和d个11来算出来需要的0的个数x，1的个数y。

找答案字符串时，凑01，这样10也满足条件。

设q = b / y，w = b % y。这样先输出时，输出q个0，输出y-w个1，这样就保证了有q*（y-w）个01，如果w == 0，表示刚好能够用上所有的1来组成01，再把剩余的输出1和0就可以了。但是如果q != x，即不需要把0全部输出，那样q*（y-w）> b，所以把0剩余提前到1前面，eg：现在有3个0，3个1，我们只需要7个01，按着这种想法，如果输出001110（代码如果没考虑）或者是000111，这样就会多答案或者少答案，所以应该是001101，所以要判断一下余下的，把0调前一个，让正好能够是7个01就可以了，相应的最后的输出0个数要-1。

其次加上特判，a、b、c、d分别为0和部分为0的时候的特判。（自己好菜。。%队友）

#include <cstdio>

#include <cstring>

#include <cmath>

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()

{

    ll a,b,c,d,abc;

    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);

    if(a==0&&b==0&&c==0&&d==0)

    {

        printf("0\n");

        return 0;

    }

    ll x,y,i;

    x = (1 + sqrt(1+8*a)) / 2;

    if(x*(x-1)/2 != a)

    {

        printf("impossible\n");

        return 0;

    }

    y = (1 + sqrt(1 + 8*d)) / 2;

    if(y*(y-1)/2 != d)

    {

        printf("impossible\n");

        return 0;

    }

    if(a == 0&&d == 0)

    {

        if(b == 1&&c == 0)

        {

            printf("0");

            printf("1\n");

        }

        else if(c == 1&&b==0)

        {

            printf("1");

            printf("0\n");

        }

        else printf("impossible\n");

        return 0;

    }

    if(b==0&&c==0)

    {

        if(a==0)

        {

            for(i=1;i<=y;i++) printf("1");

            printf("\n");

        }

        else if(d==0)

        {

            for(i=1;i<=x;i++) printf("0");

            printf("\n");

        }

        else printf("impossible\n");

        return 0;

    }

    if(x*y != b+c)

    {

        printf("impossible\n");

        return 0;

    }

    ll j,q,w;

    q = b / y;

    w = b % y;

    for(i=1;i<=q;i++) printf("0");

    for(i=1;i<=y-w;i++) printf("1");

    if(q!=x)

    printf("0");

    for(i=1;i<=w;i++) printf("1");

    for(i=1;i<=x-q-1;i++) printf("0");

    return 0;

}

巴特西

Jumbled String （Kattis - jumbledstring）(思维题)

Problem

Input

Output

最新文章

热门文章