Jumbled String

면접 대비

시간 제한1초메모리 제한512 MB

요약
00, 01, 10, 11 부분 수열의 등장 횟수가 주어질 때 이 횟수를 모두 만족하는 비트 문자열을 출력합니다.
난이도

보통10점 중 7점

유형
조합론, 그리디, 수학, 문자열
정답자
아직 제출이 없습니다

문제

문자열의 부분열이란 문자열에서 몇 개의 문자를 지워서 얻을 수 있는 문자열을 말한다. 예를 들어 "string", "sing", "i", "sg"는 모두 "string"의 부분열이다. 같은 부분열을 서로 다른 문자 집합을 지워서 정확히 tt가지 방법으로 얻을 수 있으면, 그 부분열이 tt번 나타난다고 한다.

Jingfei는 다음 성질을 만족하는 비어 있지 않은 비트 문자열을 만들려고 한다.

  1. 부분열 00이 aa번 나타난다.
  2. 부분열 01이 bb번 나타난다.
  3. 부분열 10이 cc번 나타난다.
  4. 부분열 11이 dd번 나타난다.

하지만 Jingfei는 그런 문자열을 어떻게 만드는지도, 애초에 가능한지도 모른다. 도와주자.

입력

입력은 한 줄로 주어지며, 네 정수 aa, bb, cc, dd가 공백으로 구분되어 들어온다 (0≤a,b,c,d≤1090 \le a, b, c, d \le 10^9).

출력

주어진 조건을 만족하는 비트 문자열을 출력한다. 답이 여러 개면 그중 아무거나 출력해도 된다. 답이 없으면 "impossible"을 출력한다.

예제2

  1. 예제 1

    입력
    3 4 2 1
    
    예상 출력
    01001
    
  2. 예제 2

    입력
    5 0 0 5
    
    예상 출력
    impossible