Connection Status:
Competition Arena > PerfectSequences2

PerfectSequences2

Member SRM 505 · 2010-11-01 · by ivan_metelsky

Member SRM 505 · 2010-11-01 · by ivan_metelsky · Brute Force, Math, Sorting
Class Name: PerfectSequences2
Return Type: long
Method Name: minimumMoves
Arg Types: (vector<int>)
Problem Statement

Problem Statement

A perfect sequence is a sequence such that all of its elements are integers and the product of all of them is equal to their sum. For example {1,2,3} is a perfect sequence because 1+2+3 = 1*2*3, {-1,1,-1,1,6} is a perfect sequence as well, but {4,5,6} is not a perfect sequence because 4*5*6 is not equal to 4+5+6.

You are given a int[] seq. In one move you can choose one element of seq and increase or decrease it by 1. Return the minimum number of moves required to transform seq into a perfect sequence.

Constraints

  • seq will contain between 1 and 50 elements, inclusive.
  • Each element of seq will be between -1,000,000,000 and 1,000,000,000, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{-1000000000}
Returns: 0

Any sequence consisting of 1 integer is perfect, so no additional moves are needed.

1)
{-2}
Returns: 0
2)
{-1}
Returns: 0
3)
{0}
Returns: 0
4)
{1}
Returns: 0
7)
{-1,1}
Returns: 2

There are 2 perfect sequences containing two elements: {0,0} and {2,2}. In order to obtain {0,0} from {-1,1} you need 2 moves, in order to obtain {2,2} you need 4 moves.

8)
{4,3}
Returns: 3

This time it is better to obtain {2,2}.

9)
{17,95,-79}
Returns: 33

Here the best solution is to transform seq into {0,95,-95}.

10)
{10,9,8}
Returns: 21

Decrease each element by 7 to obtain {3,2,1}.

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

Coding Area

Language: C++17 · define a public class PerfectSequences2 with a public method long long minimumMoves(vector<int> seq) · 332 test cases · 2 s / 256 MB per case

Submitting as anonymous