16324 - Jumbled String

 

 

문제 번역

subsequence :  문자열에서 일부 문자 하위 집합을 제거하여 얻은 문자열(ex. string에서 sing, i, sg 등)

0과 1로 이루어진 비어있지 않은 문자열을 만들고 싶습니다. 이때, 문자열에서 subsequence가

00인 것들의 개수, 

01인 것들의 개수, 

10인 것들의 개수, 

11인 것들의 개수가 각각 $a$, $b$, $c$, $d$였으면 합니다. 이런 조건을 만족하는 문자열을 만드세요.

step 1

$a$를 통해서 0의 개수를 알아낼 수 있습니다.

$\frac{n(n-1)}{2} = a$인 $n$이 0의 개수입니다.

같은 방법으로 1의 개수 역시 $d$를 통해 찾을 수 있습니다.

이렇게 찾은 0, 1의 개수를 각각 $n$, $m$이라고 합시다.

step 2

어떤 1을 잡았을 때 1 왼쪽에 있는 0의 개수만큼 01이 생깁니다. 1 오른쪽에 있는 0의 개수만큼 10이 생깁니다.

 

즉, {01의 개수} + {10의 개수} = $n * m$입니다. 이를 만족하지 않으면 impossible입니다.

step 3

제일 왼쪽에 있는 1은 10을 $n$개만큼 만듭니다. 제일 오른쪽에 있는 1은 10을 하나도 만들지 않습니다.

그럼 제일 왼쪽에 1을 $\lfloor {c/n} \rfloor$개 넣고 0을 $n-(c \% n)$개 넣습니다. 그 다음 1, 남은 0들, 남은 1들을 넣으면 조건을 만족할 수 있습니다.

아래는 0이 5개, 1이 5개, 10이 18개여야 할 때 상황입니다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main() {
    long long int x, y, z, w,i,n=-1,m=-1;
    scanf("%lld%lld%lld%lld", &x, &y, &z, &w);
    if (x == 0 && y == 0 && z == 0 && w == 0) {
        printf("1"); return 0;
    }
    if (x == 0) {
        if (y == 0 && z == 0) n = 0; else n = 1;
    }
    else {
        for (i = 2;i <= 1000000;i++) {
            if (i * (i - 1) / 2 > x) { printf("impossible"); return 0; }
            if (i * (i - 1) / 2 == x) { n = i; break; }
        }
    }
    if (w == 0) {
        if (y == 0 && z == 0) m = 0; else m = 1;
    }
    else {
        for (i = 2;i <= 1000000;i++) {
            if (i * (i - 1) / 2 > w) { printf("impossible"); return 0; }
            if (i * (i - 1) / 2 == w) { m = i; break; }
        }
    }
    if (n * m != y + z) { printf("impossible"); return 0; }
    if (n == 0 || m == 0) {
        for (i = 1;i <= n;i++) printf("0");
        for (i = 1;i <= m;i++) printf("1");
        return 0;
    }
    while (n+m!=0) {
        if (z >= n) { printf("1"); z -= n; m--; }
        else { printf("0"); n--; }
    }
    return 0;
}