Statistics

Problem Statement for "ChemicalMixing"

Problem Statement

Your lab has several containers of a certain type of chemical, each with varying volume, and varying quantity of dissolved solute. The strength of any container can be calculated as solute / volume. volume[i] and solute[i] represent the volume and quantity of solvent in container i.

You now wish to mix a batch of the chemical, and can do so only by using the entirety of some subset of the available containers. That is, you cannot use part of what is left in any container, you must use all or none of each container. You need to produce at least minQuantity volume total after mixing, and you want the end result to have a strength as close as possible to desiredStrength. Compute the absolute difference between the desired strength and the closest strength you can create by mixing checmicals to obtain the minimum required volume.

Definition

Class:
ChemicalMixing
Method:
closestBlend
Parameters:
int[], int[], int, double
Returns:
double
Method signature:
double closestBlend(int[] volume, int[] solute, int minVolume, double desiredStrength)
(be sure your method is public)

Notes

  • * A return value that is within 1e-9 of the actual result is considered correct.

Constraints

  • volume will have between 1 and 50 elements, inclusive.
  • Each element of volume will be between 1 and 100, inclusive.
  • solute will have the same number of elements as volume.
  • Each element of solute will be between 0 and 20, inclusive.
  • minVolume will be between 1 and the sum of all elements of volume.
  • desiredStrength will be between 0 and 10, inclusive.

Examples

  1. {10, 10}

    {1, 4}

    5

    0.20

    Returns: 0.04999999999999999

    Either container is sufficient volume on it's own, but the strength would be 0.1 or 0.4, a difference from our desired strength by 0.1 or 0.2. However, if we combine the two, the resultant strength of the chemical is 0.25, an error of only 0.05, which is better.

  2. {10, 10, 10, 10}

    { 5, 5, 5, 0}

    35

    0.5

    Returns: 0.125

    Although the first three containers are exactly the right strength, we need to mix all four containers to get a sufficient volume. The resulting strength is 0.375, an error of 0.125.

  3. { 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 23, 88}

    { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 0, 1, 2, 3, 4, 5, 6, 7, 8}

    1

    0.1

    Returns: 0.0

  4. {20, 20, 20}

    {15, 15, 0}

    40

    0.5

    Returns: 0.0

    Although any two containers would suffice to meet the required volume, if we use all three, we can precisely hit the desired strength.

  5. {50, 50, 50, 50}

    {12, 4, 20, 0}

    100

    0.5

    Returns: 0.18

  6. {25,77,2,90,35,37,65,71,9,21,80,86,46,26,74,45,26,24,26,42,66,31,60,61,88,43,31,80,67,77}

    {10,4,10,19,11,17,18,17,11,8,18,16,4,2,8,19,5,12,13,19,19,12,12,11,13,18,20,8,20,16}

    1193

    0.136380353839603

    Returns: 0.05509121806675152

  7. {95,43,39,12,46,30,89,24,86,72,8}

    {1,11,13,11,2,15,11,4,12,4,20}

    344

    0.215986296169453

    Returns: 1.520323608063534E-4

  8. {48,93,87,66,72,54,4,91,10,76,20,84,78,19,56}

    {17,5,12,18,7,3,4,15,20,0,19,8,18,11,2}

    446

    0.361103338513881

    Returns: 0.07389159847195226

  9. {27,79,28,51,90,20,4,40,48,2,62,56,50,96,11,59,2,77,13,82,26,31,64,75,80,8,97,19,36,70,65,53,58,69,6,69,17,55,80,39}

    {19,3,12,13,3,14,17,16,20,16,2,0,10,9,6,8,7,6,11,7,8,15,15,1,15,3,14,3,16,16,1,12,17,13,1,19,13,4,16,16}

    1685

    0.33652538826396

    Returns: 0.09230487848328425

  10. {37,45,31,61,36,5,19,73,82,8,72,17,32,96,55,92,77,16,14,39,46,33,12,37,8,57,70,92,8,11,24,42}

    {4,8,3,20,18,15,17,3,0,0,1,20,3,7,8,20,9,7,8,9,2,0,19,7,13,15,18,6,9,2,4,20}

    72

    0.420852167023972

    Returns: 2.7461745511492275E-6

  11. {75,39,42,61,61,13,40,59,91,18,90,85,67,25,23,36,7,62,70,16,9,32,95,71,66,52,80,7,86,38,41,34,37,80,18,60,67,22,21,33,60,59,19,29,90,82,22,70,97}

    {14,0,13,11,15,18,16,6,17,6,10,5,6,5,14,1,20,14,12,1,6,12,12,7,19,3,15,4,2,2,7,18,0,9,18,6,1,12,5,1,19,5,4,6,8,12,0,15,8}

    2222

    0.0833226631127387

    Returns: 0.04917509874939202

  12. {27,75,20,72,47,62,32,50,6,16,49,79,2,64,50,80,42,33,84,100,58,43,21,91,21,92,8,33,38,34,85,5,23,37,20,95,73,19,12,88,19}

    {3,7,10,11,0,16,10,16,15,15,11,1,2,8,13,0,5,15,19,15,16,7,16,10,19,14,3,15,13,2,6,17,12,1,15,2,8,14,8,4,2}

    1051

    0.0744653150610021

    Returns: 6.298682579035375E-5

  13. {11,28,61,18,90,25,59,61,86,47,80,66,62,97,13,73,50,13,10,60,78,84,94,54,27,34,72,92,29,31,41,47,16,24,4,35}

    {19,19,7,12,18,15,3,9,6,20,20,20,12,16,19,3,2,13,2,7,11,11,20,5,16,17,11,2,6,20,8,20,1,9,19,15}

    169

    0.352362880184844

    Returns: 6.754604345848847E-7

  14. {27,11,64,71,36,91,95,100,80,60,39,86}

    {2,0,1,10,12,9,4,8,17,20,1,8}

    571

    0.205700064409041

    Returns: 0.057616440715661216

  15. {23,44,10,33}

    {6,12,13,13}

    20

    0.79060702770511

    Returns: 0.1859558649144124

  16. {68,71,12,26,29,4,55,13,85,29,18,99,19,98,82,56,21,15,26,96,14,47,19,89,97,49,71,10,95,69,43,85,70,37,77,89,25,58,43,31,3,86,13,31,43,73,83,3,36,14}

    {19,18,8,13,5,11,19,2,4,14,18,10,19,17,12,0,10,13,10,9,4,17,16,14,10,9,9,16,4,4,9,14,0,0,9,7,17,20,3,8,5,6,1,15,7,0,15,14,16,3}

    2081

    0.166313074318963

    Returns: 8.25451870248295E-6

  17. {20, 20, 20 }

    {15, 15, 0 }

    40

    0.5

    Returns: 0.0

  18. {10, 10, 10, 10 }

    {5, 5, 5, 0 }

    35

    0.5

    Returns: 0.125

  19. {10, 10 }

    {1, 4 }

    5

    0.2

    Returns: 0.04999999999999999

  20. {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }

    {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 }

    4000

    10.0

    Returns: 9.8

  21. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    {1, 1, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 20, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11 }

    10

    1.0

    Returns: 0.0

  22. {50, 50, 50, 50 }

    {12, 4, 20, 0 }

    100

    0.5

    Returns: 0.18

  23. {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }

    {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 }

    1

    5.0

    Returns: 4.8

  24. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

    6

    3.14159265358

    Returns: 7.475831574650371E-4

  25. {100, 100, 100, 100, 100, 100, 50, 50, 50, 20, 100, 100, 100, 100, 100, 100, 50, 50, 50, 20, 100, 100, 100, 100, 100, 100, 50, 50, 50, 20, 100, 100, 100, 100, 100, 100, 50, 50, 50, 20, 100, 100, 100, 100, 100, 100, 50, 50, 50, 20 }

    {20, 20, 15, 20, 19, 20, 12, 0, 4, 1, 20, 20, 15, 20, 19, 20, 12, 0, 4, 1, 20, 20, 15, 20, 19, 20, 12, 0, 4, 1, 20, 20, 15, 20, 19, 20, 12, 0, 4, 1, 20, 20, 15, 20, 19, 20, 12, 0, 4, 1 }

    1000

    9.99

    Returns: 9.780476190476191

  26. {84, 87, 78, 16, 94, 36, 87, 93, 50, 22, 63, 28, 91, 60, 64, 27, 41, 27, 73, 37, 12, 69, 68, 30, 83, 31, 63, 24, 68, 36, 30, 3, 23, 59, 70, 68, 94, 57, 12, 43, 30, 74, 22, 20, 85, 38, 99, 25, 16, 71 }

    {17, 19, 7, 8, 8, 9, 11, 11, 1, 10, 9, 6, 11, 12, 17, 5, 19, 18, 10, 14, 12, 3, 9, 3, 17, 9, 11, 14, 9, 14, 7, 3, 12, 14, 11, 18, 0, 2, 8, 1, 12, 18, 5, 0, 7, 1, 4, 6, 18, 14 }

    2000

    4.0

    Returns: 3.769345981028457

  27. {10, 20 }

    {5, 20 }

    1

    0.5

    Returns: 0.0

  28. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1 }

    50

    5.5

    Returns: 4.5

  29. {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }

    {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 }

    5000

    0.21

    Returns: 0.009999999999999981

  30. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33 }

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    1

    1.0

    Returns: 0.0

  31. {3, 2, 2 }

    {10, 0, 1 }

    4

    0.25

    Returns: 0.0

  32. {9, 17 }

    {6, 8 }

    13

    0.5

    Returns: 0.02941176470588236

  33. {10, 10 }

    {1, 20 }

    10

    0.1

    Returns: 0.0

  34. {1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 9, 9, 11, 14, 1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 85, 4, 3, 44, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }

    {2, 3, 2, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 5, 5, 2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5 }

    10

    2.5

    Returns: 0.8999999999999999

  35. {1 }

    {1 }

    1

    1.0

    Returns: 0.0

  36. {96, 86, 95, 95, 98, 87, 86, 95, 91, 96, 89, 85, 87, 89, 95, 96, 90, 98, 85, 87, 89, 98, 84, 99, 84, 86, 95, 82, 94, 98, 84, 90, 99, 91, 89, 88, 86, 93, 82, 85, 92, 83, 96, 86, 85, 99, 84, 91, 82, 96 }

    {17, 12, 14, 13, 15, 16, 19, 15, 15, 19, 15, 19, 19, 16, 17, 14, 11, 13, 11, 18, 19, 11, 19, 15, 15, 12, 15, 11, 15, 11, 10, 15, 17, 20, 16, 12, 10, 12, 16, 20, 16, 11, 12, 13, 14, 13, 19, 15, 20, 14 }

    1337

    0.17421337666

    Returns: 2.2861074450153396E-8

  37. {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99 }

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 0, 1, 2, 3, 4, 5, 6, 7 }

    1

    0.12345

    Returns: 1.691093573924496E-7

  38. {93, 65, 17, 78, 85, 37, 92, 82, 64, 6, 20, 26, 24, 11, 54, 86, 39, 66, 77, 4, 47, 71, 80, 89, 71, 59, 88, 17, 28, 100, 62, 39, 80, 18, 75, 80, 26, 20, 68, 67, 11, 90, 63, 28, 36, 85, 12, 17, 86, 20 }

    {10, 11, 18, 6, 20, 12, 7, 7, 16, 13, 5, 6, 19, 3, 20, 10, 9, 18, 3, 19, 14, 17, 1, 9, 3, 8, 2, 4, 14, 17, 7, 7, 8, 17, 9, 12, 4, 8, 18, 3, 19, 0, 3, 9, 5, 0, 7, 10, 4, 3 }

    2000

    1.0

    Returns: 0.7727047146401985

  39. {1, 2 }

    {1, 3 }

    1

    1.0

    Returns: 0.0

  40. {96, 86, 95, 95, 98, 87, 86, 95, 91, 96, 89, 85, 87, 89, 95, 96, 90, 98, 85, 87, 89, 98, 84, 99, 84, 86, 95, 82, 94, 98, 84, 90, 99, 91, 89, 88, 86, 93, 82, 85, 92, 83, 96, 86, 85, 99, 84, 91, 82, 96 }

    {17, 12, 14, 13, 15, 16, 19, 15, 15, 19, 15, 19, 19, 16, 17, 14, 11, 13, 11, 18, 19, 11, 19, 15, 15, 12, 15, 11, 15, 11, 10, 15, 17, 20, 16, 12, 10, 12, 16, 20, 16, 11, 12, 13, 14, 13, 19, 15, 20, 14 }

    4200

    0.17421337666

    Returns: 0.005578516008134166

  41. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    10

    4.0

    Returns: 2.0

  42. {93, 65, 17, 78, 85, 37, 92, 82, 64, 6, 20, 26, 24, 11, 54, 86, 39, 66, 77, 4, 47, 71, 80, 89, 71, 59, 88, 17, 28, 100, 62, 39, 80, 18, 75, 80, 26, 20, 68, 67, 11, 90, 63, 28, 36, 85, 12, 17, 86, 20 }

    {10, 11, 18, 6, 20, 12, 7, 7, 16, 13, 5, 6, 19, 3, 20, 10, 9, 18, 3, 19, 14, 17, 1, 9, 3, 8, 2, 4, 14, 17, 7, 7, 8, 17, 9, 12, 4, 8, 18, 3, 19, 0, 3, 9, 5, 0, 7, 10, 4, 3 }

    2000

    0.123456

    Returns: 7.90123456786973E-7

  43. {100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51 }

    {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 }

    1

    1.0

    Returns: 0.607843137254902

  44. {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }

    {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 }

    100

    0.3

    Returns: 0.09999999999999998

  45. {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }

    {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 }

    5000

    10.0

    Returns: 9.8

  46. {2 }

    {1 }

    1

    0.0

    Returns: 0.5

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: