PerfectSequences2
Member SRM 505 · 2010-11-01 · by ivan_metelsky
Member SRM 505 · 2010-11-01 · by ivan_metelsky · Brute Force, Math, Sorting
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 aint[] 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.
You are given a
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.
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