Numb

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

요약

길이가 n인 이진수를 만들어, 모든 접두사가 n으로 나눈 나머지가 서로 다르고 전체 수가 n으로 나누어떨어지도록 한다.

난이도: 보통10점 중 6점
유형: 그리디, 수학, 정수론, 구현
정답자: 아직 제출이 없습니다

문제

짝수 정수 $n$ 이 주어진다. $n$ 개의 이진 자리로 이루어진 이진수 $a = \overline{a_1 a_2 \ldots a_n}$ 을 만들어, $a$ 가 $n$ 으로 나누어떨어지고, $i = 1, 2, \ldots, n$ 에 대한 모든 수 $\overline{a_1 a_2 \ldots a_i}$ ( $a$ 의 이진 표기에서 앞에서부터 $i$ 자리까지의 접두사)가 $n$ 으로 나눈 나머지가 서로 다르도록 하라.

입력

첫째 줄에 정수 $n$ 이 주어진다. ( $2 \le n \le 1000$ , $n$ 은 짝수)

출력

조건을 만족하는 수 $\overline{a_1 a_2 \ldots a_n}$ 을 $n$ 자리 이진 문자열로 출력한다. 앞에 오는 0은 허용되지 않는다. 가능한 답이 여러 개라면 아무거나 하나 출력한다. 이 제약 조건에서 답이 적어도 하나 존재함이 보장된다.

예제2

예제 1
입력
```
2
```
예상 출력
```
10
```
예제 2
입력
```
4
```
예상 출력
```
1100
```