2001년 가을학기 문제해결기법 - 문제 4

숫자 대응 문제

N이 n이하인 양의 정수 집합 {1, 2, 3, ···, n}을 나타낸다고 하자. 우리는 다음 조건을 만족하는 일대일 대응 함수 F: N → N을 구하고자 한다.

조건: 모든 i에 대해서 i+F(i) = 2k를 만족하는 정수 k, k≥1가 존재한다, 1≤i≤n.

즉, N에 속한 모든 i에 대해 i와 그에 대응하는 함수값 F(i)를 더한 값이 2의 거듭제곱(power)인 형태의 값이 되어야 함을 말한다. 예를 들어 n=5인 경우에 위의 조건을 만족하는 일대일 대응 함수가 다음과 같이 존재한다.

i        1    2    3    4    5

□    □    □    □    □

□    □    □    □    □

□    □    □    □    □

F(i)     1    2    5    4    3

위의 예에서 1+1 = 21, 2+2 = 22, 3+5 = 23, 4+4 = 23, 5+3 = 23이므로 이러한 대응이 위의 조건을 만족함을 알 수 있다.

n이 주어졌을 때, 위의 조건을 만족하는 일대일 대응 함수를 출력하는 프로그램을 작성하시오.

프로그램명은 mapping.c(mapping.cpp)라고 하고 실행 파일명은 mapping.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에는 첫줄에 n이 주어진다. n은 1000이하인 양의 정수이다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 문제의 조건을 만족하는 숫자 대응이 존재하지 않을 때는 첫째 줄에 impossible이라고 출력한다. 숫자 대응이 존재하는 경우는 출력 파일의 첫째 줄에 n을 출력하고, 둘째 줄부터 n+1째 줄까지 일대일 대응 함수를 출력하는데, i+1번째 줄에 i에 대응되는 F(i)를 출력한다. 답이 하나 이상일 때는, 하나만 출력하면 된다.

입력과 출력의 예

INPUT.TXT

5

OUTPUT.TXT

5

1

2

5

4

3