Palindromic Integer Partition

View as PDF

Submit solution

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 an number N, please find the number of different palindromic partitions.

Note: For partitions, the numbers must be POSITIVE INTEGERS

Subtasks

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.