KOISTUDY

Informatica Online Judge

이진 암호화 [0970 / 03CA]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 84 Total Tried : 131

The Champion of this Problem (C++) : gs18012 - 0ms / 394byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

이진 압축이란 {0, 1}로 이루어진 길이가 2^k인 문자열에 대해서, 모두 같은 문자가 될 때까지 크기가 2^(k-1)인 두 그룹으로 분할하여 모두 같은 문자가 되도록 하는 과정으로 암호화를 한다.

만약 주어진 원문이 길이가 4인

0000

라면, 암호문은

0

이다.

만약 주어진 암호문이 길이가 4인

1101

이라면 모든 문자가 같지 않기 때문에

11 01

로 일단 한 번 분할하고

다시 뒷 부분은 01로 같지 않으니

11 0 1

로 분할한다.

즉 이로써 만들어진 암호문은

-1-01

이 된다.

-1-01의 의미는

- : 먼저 전체를 분할하고
1 : 분할된 왼쪽 부분은 모두 1이고
- : 오른쪽 분할은 다시 분할하며,
01 : 분할된 결과는 0과 1이라는 의미이다.

길이가 n인 원문을 입력받아서 암호문을 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 암호문의 길이 n이 입력된다.
두 번째 줄에 길이가 n인 0, 1로 구성된 암호문이 입력된다.

[입력값의 정의역]
1 <= n <= 2^18 (단, n은 모두 2^k (k는 음이 아닌 자연수))

Output

위 원리로 만들어진 암호문을 출력한다.

IO Example