RoyalTreasurer
SRM 433 · 2009-01-21 · by gojira_tc
SRM 433 · 2009-01-21 · by gojira_tc · Simple Search, Iteration, Sorting
Problem Statement
Problem Statement
Once upon a time, there was a kingdom where math was always a big problem. When the post of the royal treasurer needed to be filled, applicants were presented with the following problem:
"We have two arrays of integers, A and B. A and B each contain exactly N elements. Let's define a function S over A and B:
The problem writers need a program to check the correctness of the applicants' answers. Givenint[] s A and B, return the smallest possible value for S.
"We have two arrays of integers, A and B. A and B each contain exactly N elements. Let's define a function S over A and B:
S = A0*B0 + ⦠+ AN-1*BN-1Rearrange the numbers in A in such a way that the value of S is as small as possible. You are not allowed to rearrange the numbers in B.â
The problem writers need a program to check the correctness of the applicants' answers. Given
Constraints
- A will contain between 1 and 50 elements, inclusive.
- A and B will contain the same number of elements.
- Each element of A will be between 0 and 100, inclusive.
- Each element of B will be between 0 and 100, inclusive.
Examples
0)
{1,1,3}
{10,30,20}
Returns: 80
If you move the number 3 to the beginning of A, you get the minimal possible sum.
1)
{1,1,1,6,0}
{2,7,8,3,1}
Returns: 18
The best option would be to rearrange the numbers in A this way: {1,1,0,1,6}.
2)
{5,15,100,31,39,0,0,3,26}
{11,12,13,2,3,4,5,9,1}
Returns: 528
3)
{3,100,99,100,100}
{0,31,99,1,21}
Returns: 5566
4)
{100}
{0}
Returns: 0
Submissions are judged against all 66 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RoyalTreasurer with a public method int minimalArrangement(vector<int> A, vector<int> B) · 66 test cases · 2 s / 256 MB per case