제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

디미고의 학교 로고는 0과 1을 이용해 D를 @ 모양으로 형상화한 도형이다. 이러한 점에서 착안해 모든 원소가 0 또는 1인 길이가 N인 수열 A가 다음과 같은 작업을 K번 반복했을 때 A의 길이가 0이 되는 A를 DIMI Sequences라고 한다. 만약 K번째 작업 이전에 A의 길이가 0이 될 경우 작업을 시행할 수 없으므로 DIMI Sequences가 아니다.

S를 A의 맨 앞 원소, E를 A의 맨 뒤 원소라고 할 때, S와 E의 값에 따라 다음 작업 중 한 가지를 시행한다.

• S=@이라면 S를 삭제하고 E를 반전시킨다.

• E=@이라면 E를 삭제하고 S를 반전시킨다.

• S=0,\ E=0이라면 맨 앞에 1을 추가한다.

• S=1,\ E=1이라면 맨 뒤에 0을 추가한다.

• S=0,\ E=1또는 S=1,\ E=0 이라면 S와 E 중 더 큰 원소를 @로 변경하고 작은 원소는 삭제한다.

반전 연산은 0→1,\ 1→0으로 바꾸는 연산을 의미한다. 또한, 연산의 특성상 S=@이면서 E=@인 경우는 존재하지 않는다.

단, A의 길이가 1인 경우에는 항상 S=E이기 때문에 작업은 다음과 같이 진행된다.

• S=@→S를 삭제한다. 반전할 원소가 존재하지 않으므로 작업을 종료한다.

• S=0→맨 앞에 1를 추가한다.

• S=1→맨 뒤에 0를 추가한다.

DIMI Sequences의 조건을 만족하는 A를 구하시오.