Palindromic Integer Partition

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.5s
Memory limit: 64M

Author:
Problem types

A partition of an integer N is a series of numbers that add up to N. For example, given the number 15, an partition could be 1 + 2 + 3 + 4 + 5, which adds up to 15. A palindromic partition is when that series of numbers is a palindrome. For example, a palindromic partition of the number 15 can be 3 + 9 + 3.

To be specific, a palindrome series of numbers count the numbers as individual characters, so the palindromic series 10 + 1 + 10 will work if the number is 21, and just 21 will also work for the same case (shown in sample).

Given a number N, please find the number of different palindromic partitions.

Note: For partitions, the numbers must be POSITIVE INTEGERS.

Constraints

Subtask 1 [30%]

1 \le N \le 10

Subtask 2 [50%]

1 \le N \le 50

Subtask 3 [20%]

1 \le N \le 63

Input Specification

One integer N.

Output Specification

One integer M, the number of different palindromic partitions.

Sample Input

7

Sample Output

8

Explanation of Sample

The palindromic partitions of 7 are:

7 = 7
7 = 1 + 5 + 1
7 = 2 + 3 + 2
7 = 3 + 1 + 3
7 = 1 + 1 + 3 + 1 + 1
7 = 2 + 1 + 1 + 1 + 2
7 = 1 + 2 + 1 + 2 + 1
7 = 1 + 1 + 1 + 1 + 1 + 1 + 1

In total, there are 8 palindromic partitions.


Comments

There are no comments at the moment.