3414 - 재귀적 회문 덧셈 수식 찾기

• Submit
• Status
• Discuss
• Summary

Description

딘일 자연수 N이 있을 때, N을 구하는 자연수의 덧셈 수식은 유한개가 존재합니다. 예를 들어 15를 구하는 덧셈 수식은,

15 = 1+2+3+4+5 = 1+2+1+7+1+2+1 ...

등과 같이 구할 수 있습니다.

앞으로 읽거나, 뒤로 읽어도 같은 수식을 회문 수식이라고 합니다. 위 예제에서 "1+2+3+4+5"는 앞으로 읽을떄("1+2+3+4+5")와 뒤로 읽을때("5+4+3+2+1")가 서로 다르므로 회문 수식이 아닙니다. "1+2"1+7+1+2+1"의 경우 앞으로 읽어도, 뒤로 읽어도 동일하므로 회문 수식입니다. 회문 수식이 m개의 숫자로 이루어 질때, 좌측 절반의 숫자는 오른쪽 절반의 반대입니다.

재귀적 회문 수식은, 수식의 좌측 부분, 즉 시작부터 floor(2/m)개까지의 숫자로 잘라냈을 때, 그 자체도 재귀적 회문 수식의 형태를 가질때 입니다.

특정 자연수 N 이 주여졌을 때 존재하는 재귀적 회문 덧셈 수식의 개수를 구해보세요!

예를 들어 자연수 7에 대한 재귀적 회문 덧셈 수식은 다음과 같이 존재합니다.

1. 7
2. 1+5+1
3. 2+3+2
4. 1+1+3+1+1
5. 3+1+3
6. 1+1+1+1+1+1+1

회문 수식이지만, 재귀적 회문 수식이 아닌 예는 다음과 같습니다.

1. 1+2+1+2+1 (1+2는 회문 수식이 아님)
2. 2+1+1+1+2 (2+1은 회문 수식이 아님)

(첫번쨰 케이스와 마지막 케이스는 N>1인 모든 숫자에서 발생합니다.)

Input

* Line 1 : 단일 정수 N (문제의 수, 최대 1000)

* Line 2 ~ N+1 : 단일 정수 x (문제 입력 값)

Output

* Line 1 ~ N : 2개의 정수 i num

    - i : 문제 번호

    - num : 회문 덧셈 수식의 개수

Sample Input

3 
4 
7 
20

Sample Output

1 4 
2 6 
3 60