Zonal Computing Olympiad 2015, 29 Nov 2014
A sequence of positive integers is a palindrome if it reads the same in both directions. The sequences 23, 45, 23 and 23, 45, 56, 23, 23, 56, 45, 23 are examples of palindromes. The sequence 23, 45, 56 is not a palindrome. The sequence 23, 32 is not a palindrome either. A sequence of length 1 is always a palindrome.
A given sequence of integers can be broken up into parts such that each of them is a palindrome. Consider the sequence 34,45,34,56,34. This can be broken up into 3 palindrome sequences with 34, 45, 34 constituting the first, 56 constituting the second and 34 constituting the third. It can also be broken in 5 palindrome sequences each containing a single number. Thus, there may be many different ways to break up a given sequence into palindrome sequences. We want to determine the smallest number C such that the given sequence can be broken up into C palindrome sequences.
Observe that for any palindrome sequence the value of C is 1. For the sequence 34, 45, 34, 56, 34 the answer is 3. Your aim is to write a program that computes this number for any given sequence.
The first line contains N, the number of values in the sequence.
This is followed by a line containing N positive integers separated by space giving the values of the sequence.
Output a single integer giving the smalllest number C so that the given sequence can broken up into Cpalindrome sequences.
You may assume that all integers in the input are in the range 1 to 10^8 inclusive.
Subtask 1 (100 marks) : 1 ≤ N ≤ 300.
5 34 45 34 56 34
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, C99 strict, CPP 4.3.2, CPP 4.9.2, CPP14, JAVA, PYTH, PYTH 3.4|
Fetching successful submissions