Connection Status:
Competition Arena > NumericalSequence

NumericalSequence

SRM 259 · 2005-08-22 · by Andrew_Lazarev

SRM 259 · 2005-08-22 · by Andrew_Lazarev · Greedy
Class Name: NumericalSequence
Return Type: int
Method Name: makePalindrome
Arg Types: (vector<int>)
Problem Statement

Problem Statement

A numerical sequence is called a palindrome if the reverse of the sequence is the same as the original. For example sequences {1, 2, 1}, {15, 78, 78, 15} and {112} are palindromes, but {1, 2, 2}, {15, 78, 87, 51} and {112, 2, 11} are not.

You will be given a int[] sequence. You can replace any two adjacent numbers with their sum. Your method should return a minimal number of such operations required to make the given sequence a palindrome.

Constraints

  • sequence will contain between 1 and 50 elements, inclusive.
  • Each element of sequence will be between 1 and 10000, inclusive.
Examples
0)
{15,78,78,15}
Returns: 0

The sequence is a palindrome already.

1)
{1,1,1,3}
Returns: 2

We should replace two ones with 2 and afterwards replace 2 and 1 with 3.

2)
{15,78,87,51}
Returns: 3
3)
{3,23,21,23,42,39,63,76,13,13,13,32,12,42,26}
Returns: 8
4)
{1}
Returns: 0

Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NumericalSequence with a public method int makePalindrome(vector<int> sequence) · 83 test cases · 2 s / 256 MB per case

Submitting as anonymous