Jumbled String【Gym - 10193J】【2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018) 】

題目連結

  題目讓你求一個字元串是否符合這樣條件——有a個“00”串，與b個“01”，c個“10”串以及d個“11”串這樣的組成串是否存在。

  我利用了數學的知識來求這道題，假設這樣的式子成立，那麼我們假設成立字元串中有n個‘0’與m個‘1’，那麼我們可以知道對于“00”串的個數為n*(n-1)/2，對于“11”串的個數為m*(m-1)/2，“01”串與“10”串的個數總和為n*m；是以我們可以利用這個等式來确定是否可以有解。那麼n、m的值如何确定？n=sqrt(2*a)+1;m=sqrt(2*d)+1。然後以此判斷是否成立就行，但是還有另外的條件，需要特判的是a、b、c均等于0且d!=0或者b、c、d均等于0而a!=0的情況，其餘就沒有坑點了。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
int A, B, C, D;
int n, m;       //n個‘0’、m個‘1’
bool check()
{
    n=m=0;
    if(B | C)
    {
        n=(int)sqrt(2*A)+1;
        if(2*A!=n*(n-1)) return false;
        
        m=(int)sqrt(2*D)+1;
        if(2*D!=m*(m-1)) return false;
    }
    if( (B+C)!=n*m ) return false;
    if(!n && !m) return false;
    return true;
}
int main()
{
    while(scanf("%d%d%d%d",  &A, &B, &C, &D)!=EOF)
    {
        if(!A && !B && !C)
        {
            m=(int)sqrt(2*D)+1;
            if(m*(m-1)==2*D)
            {
                for(int i=1; i<=m; i++) printf("1");
                printf("\n");
            }
            else
            {
                printf("impossible\n");
            }
            continue;
        }
        if(!D && !B && !C)
        {
            n=(int)sqrt(2*A)+1;
            if(2*A==n*(n-1))
            {
                for(int i=1; i<=n; i++) printf("0");
                printf("\n");
            }
            else
            {
                printf("impossible\n");
            }
            continue;
        }
        if(!check()) { printf("impossible\n"); continue; }
        if(!m)
        {
            for(int i=1; i<=n; i++) printf("0");
            printf("\n");
        }
        else if(!n)
        {
            for(int i=1; i<=n; i++) printf("1");
            printf("\n");
        }
        else
        {
            int num = C/n;
            if(C%n==0)
            {
                for(int i=1; i<=num; i++) printf("1");
                for(int i=1; i<=n; i++) printf("0");
                int rest = m - num;
                for(int i=1; i<=rest; i++) printf("1");
                printf("\n");
                continue;
            }
            int tmp = n - ( C - num*n );
            for(int i=1; i<=num; i++) printf("1");
            for(int i=1; i<=tmp; i++) printf("0");
            printf("1");
            for(int i=1; i<=n - tmp; i++) printf("0");
            int rest = m - num - 1;
            for(int i=1; i<=rest; i++) printf("1");
            printf("\n");
        }
    }
    return 0;
}