BobTheBuilder
Cognizance - Insomnia · 2019-04-11 · by AVP_97
Problem Statement
Bob The Builder has N boxes. Each box has a happiness level. Let A[0],A[1],....A[N - 1] be the cost of N boxes. Bob wants to make beautiful box towers using all the boxes. A box tower is formed by putting boxes one above the other. And a tower is beautiful only if every boxâs happiness divides happiness value of each of the boxes above it. Bob can make any number of towers. The cost of making a tower is the maximum box happiness present in the tower.
Help Bob by calculating the minimum cost required to form towers using all the boxes.
Constraints
- The number of boxes, N is between 1 and 400 (inclusive).
- The happiness level of boxes, Ai is between 1 and 109 (inclusive).
4
{9,12,24,36}
Returns: 60
We can make 2 towers as follows : The first tower consisting of numbers {36, 9} and the second tower of numbers {24, 12}. So the total cost is 36 + 24 = 60.
10
{4772645,33887245,3896612,2973,2913,16127339,4714205,1954,974069,971}
Returns: 64379955
10
{6819071,5946,18620969,2991,14611035,21953339,2940153,5898,4940135,4955}
Returns: 69896546
10
{7744696,4870345,23234088,16127339,4885,1982,9486670,14317395,28421479,4855}
Returns: 96459298
100
{6,1,17,23,9,27,11,29,20,20,5,31,39,35,19,17,18,22,43,7,46,46,28,46,3,33,10,29,10,29,45,21,44,50,5,4,34,23,45,15,38,9,38,14,45,44,12,37,42,34,10,40,23,6,36,31,33,32,11,18,45,16,40,5,27,29,13,23,39,24,31,36,25,26,43,8,41,38,32,23,47,42,39,41,46,24,50,16,36,41,17,31,46,40,12,13,20,16,25,44}
Returns: 847
Submissions are judged against all 14 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BobTheBuilder with a public method long long minimumCost(int N, vector<int> A) · 14 test cases · 2 s / 256 MB per case