Statistics

Problem Statement for "IngredientProportions"

Problem Statement

Your friend has invented a splendid cocktail consisting of N ingredients. However, she has forgotten the amount of each ingredient that goes into the recipe.

For N-1 pairs of ingredients, she remembers the proportion in which the ingredients within each pair should be added to the cocktail. Fortunately, these N-1 proportions are sufficient to restore the recipe of the entire cocktail.

You are given a String[] proportions containing the N-1 proportions. Each element is formatted "#<a> and #<b> as <p>:<q>" (quotes for clarity), which means that the mass of ingredient <a> divided by the mass of ingredient <b> in the cocktail must be equal to <p>/<q> (all ingredients are 0-indexed). Return a int[] containing exactly N elements, where the i-th element is the mass of ingredient i, such that all the given proportions are satisfied and the total mass is as small as possible. The total mass must be greater than 0.

Definition

Class:
IngredientProportions
Method:
getMasses
Parameters:
String[]
Returns:
int[]
Method signature:
int[] getMasses(String[] proportions)
(be sure your method is public)

Constraints

  • proportions will contain between 1 and 9 elements, inclusive.
  • proportions will contain exactly N-1 elements, where N is the number of ingredients in the cocktail.
  • Each element of proportions will contain exactly 16 characters.
  • Each element of proportions will be formatted as described in the statement.
  • Each <a> will be between 0 and N-1, inclusive.
  • Each <b> will be between 0 and N-1, inclusive.
  • Each <p> will be between 1 and 9, inclusive.
  • Each <q> will be between 1 and 9, inclusive.
  • The information given in proportions will be sufficient to restore the recipe of the cocktail uniquely up to a constant factor.

Examples

  1. {"#0 and #1 as 6:4"}

    Returns: {3, 2 }

    Taking 6 units of ingredient #0 and 4 units of ingredient #1 would satisfy the proportion, but it wouldn't give the smallest possible total mass. To minimize the total mass, divide the masses by 2.

  2. {"#0 and #1 as 9:8","#1 and #2 as 9:8"}

    Returns: {81, 72, 64 }

  3. {"#4 and #0 as 1:1", "#4 and #1 as 3:1", "#4 and #2 as 5:1", "#4 and #3 as 7:1"}

    Returns: {105, 35, 21, 15, 105 }

    The mass of ingredient #4 should be divisible by 3, 5 and 7. The smallest such number is 105.

  4. {"#2 and #3 as 6:8", "#0 and #1 as 9:3", "#3 and #0 as 7:5"}

    Returns: {60, 20, 63, 84 }

  5. {"#0 and #1 as 9:9"}

    Returns: {1, 1 }

  6. {"#1 and #0 as 9:1"}

    Returns: {1, 9 }

  7. {"#0 and #1 as 6:9", "#1 and #2 as 8:6"}

    Returns: {8, 12, 9 }

  8. {"#0 and #1 as 1:5", "#5 and #4 as 4:2", "#2 and #1 as 3:3", "#3 and #4 as 4:2", "#1 and #4 as 5:1"}

    Returns: {1, 5, 5, 2, 1, 2 }

  9. {"#0 and #2 as 5:6", "#2 and #4 as 6:7", "#1 and #3 as 6:8", "#3 and #5 as 8:9", "#3 and #2 as 8:9"}

    Returns: {15, 12, 18, 16, 21, 18 }

  10. {"#1 and #4 as 1:9", "#0 and #1 as 1:9", "#9 and #6 as 8:3", "#2 and #6 as 2:8", "#5 and #8 as 5:1", "#8 and #7 as 5:1", "#3 and #4 as 1:6", "#9 and #3 as 6:1", "#3 and #5 as 1:7"}

    Returns: {800, 7200, 6075, 10800, 64800, 75600, 24300, 3024, 15120, 64800 }

  11. {"#3 and #5 as 1:7", "#9 and #6 as 8:3", "#9 and #3 as 6:1", "#1 and #4 as 1:9", "#8 and #7 as 5:1", "#5 and #8 as 5:1", "#0 and #1 as 1:9", "#2 and #6 as 2:8", "#3 and #4 as 1:6"}

    Returns: {800, 7200, 6075, 10800, 64800, 75600, 24300, 3024, 15120, 64800 }

  12. {"#7 and #1 as 9:1", "#1 and #8 as 9:1", "#7 and #5 as 1:9", "#4 and #2 as 9:1", "#3 and #9 as 9:1", "#6 and #4 as 9:1", "#6 and #0 as 1:9", "#3 and #2 as 1:9", "#9 and #5 as 9:1"}

    Returns: {387420489, 9, 531441, 59049, 4782969, 729, 43046721, 81, 1, 6561 }

  13. {"#7 and #3 as 7:1", "#1 and #4 as 1:1", "#9 and #5 as 1:8", "#7 and #8 as 1:5", "#5 and #6 as 1:8", "#2 and #9 as 1:7", "#2 and #1 as 5:1", "#8 and #4 as 1:8", "#6 and #0 as 1:5"}

    Returns: {3136000, 280, 1400, 1, 280, 78400, 627200, 7, 35, 9800 }

  14. {"#1 and #9 as 6:6", "#0 and #7 as 2:1", "#8 and #4 as 7:6", "#3 and #7 as 2:5", "#9 and #0 as 5:5", "#1 and #2 as 6:2", "#5 and #6 as 4:5", "#8 and #3 as 3:6", "#4 and #5 as 3:4"}

    Returns: {210, 210, 70, 42, 18, 24, 30, 105, 21, 210 }

  15. {"#0 and #1 as 9:1", "#1 and #2 as 9:1", "#3 and #2 as 1:9", "#4 and #3 as 1:9", "#4 and #5 as 9:1", "#5 and #6 as 9:1", "#7 and #6 as 1:9", "#7 and #8 as 9:1", "#9 and #8 as 1:9"}

    Returns: {387420489, 43046721, 4782969, 531441, 59049, 6561, 729, 81, 9, 1 }

  16. {"#1 and #0 as 1:4", "#0 and #2 as 4:2", "#0 and #3 as 4:3", "#0 and #4 as 4:4", "#5 and #0 as 5:4", "#6 and #0 as 6:4", "#0 and #7 as 4:7", "#0 and #8 as 4:8", "#0 and #9 as 4:9"}

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

  17. {"#1 and #0 as 1:1", "#0 and #2 as 2:1", "#3 and #0 as 1:3", "#4 and #0 as 1:4", "#0 and #5 as 5:1", "#0 and #6 as 6:1", "#7 and #0 as 1:7", "#0 and #8 as 8:1", "#9 and #0 as 1:9"}

    Returns: {2520, 2520, 1260, 840, 630, 504, 420, 360, 315, 280 }

  18. {"#5 and #9 as 8:5", "#6 and #9 as 9:6", "#3 and #9 as 8:4", "#9 and #4 as 7:7", "#0 and #7 as 4:6", "#1 and #0 as 7:5", "#8 and #0 as 4:8", "#2 and #0 as 8:4", "#2 and #3 as 7:9"}

    Returns: {70, 98, 140, 180, 90, 144, 135, 105, 35, 90 }

  19. {"#8 and #0 as 4:8", "#1 and #0 as 7:5", "#5 and #9 as 8:5", "#3 and #9 as 8:4", "#2 and #0 as 8:4", "#6 and #9 as 9:6", "#9 and #4 as 7:7", "#2 and #3 as 7:9", "#0 and #7 as 4:6"}

    Returns: {70, 98, 140, 180, 90, 144, 135, 105, 35, 90 }

  20. {"#9 and #3 as 9:1", "#9 and #1 as 1:8", "#1 and #0 as 1:7", "#0 and #2 as 1:8", "#2 and #4 as 1:9", "#9 and #8 as 1:5", "#6 and #1 as 7:8", "#0 and #5 as 9:4", "#2 and #7 as 5:3"}

    Returns: {2520, 360, 20160, 5, 181440, 1120, 315, 12096, 225, 45 }

  21. {"#6 and #1 as 7:8", "#2 and #4 as 1:9", "#0 and #2 as 1:8", "#0 and #5 as 9:4", "#9 and #8 as 1:5", "#1 and #0 as 1:7", "#9 and #1 as 1:8", "#2 and #7 as 5:3", "#9 and #3 as 9:1"}

    Returns: {2520, 360, 20160, 5, 181440, 1120, 315, 12096, 225, 45 }

  22. {"#1 and #0 as 7:5", "#3 and #2 as 4:9", "#6 and #1 as 7:8", "#3 and #5 as 6:5", "#8 and #9 as 9:7", "#3 and #0 as 5:8", "#7 and #4 as 2:9", "#4 and #9 as 8:3", "#1 and #8 as 5:7"}

    Returns: {194400, 272160, 273375, 121500, 790272, 101250, 238140, 175616, 381024, 296352 }

  23. {"#3 and #6 as 3:6", "#5 and #3 as 7:5", "#4 and #2 as 4:7", "#1 and #5 as 3:8", "#1 and #7 as 8:9", "#2 and #3 as 8:9", "#8 and #4 as 5:9", "#9 and #3 as 4:1", "#0 and #7 as 1:2"}

    Returns: {107163, 190512, 322560, 362880, 184320, 508032, 725760, 214326, 102400, 1451520 }

  24. {"#5 and #4 as 8:7", "#1 and #3 as 3:5", "#5 and #6 as 7:1", "#7 and #6 as 8:9", "#4 and #2 as 2:9", "#7 and #0 as 7:2", "#2 and #3 as 4:9"}

    Returns: {5120, 750141, 555660, 1250235, 123480, 141120, 20160, 17920 }

  25. {"#2 and #3 as 6:8", "#0 and #1 as 9:3", "#3 and #0 as 7:5" }

    Returns: {60, 20, 63, 84 }

  26. {"#0 and #1 as 9:8", "#1 and #2 as 9:8", "#2 and #3 as 9:8", "#3 and #4 as 9:8", "#4 and #5 as 9:8", "#5 and #6 as 9:8", "#6 and #7 as 9:8", "#7 and #8 as 9:8", "#8 and #9 as 9:8" }

    Returns: {387420489, 344373768, 306110016, 272097792, 241864704, 214990848, 191102976, 169869312, 150994944, 134217728 }

  27. {"#4 and #0 as 1:1", "#4 and #1 as 3:1", "#4 and #2 as 5:1", "#4 and #3 as 7:1" }

    Returns: {105, 35, 21, 15, 105 }

  28. {"#0 and #1 as 1:2", "#1 and #2 as 2:3", "#2 and #3 as 3:4", "#3 and #4 as 4:5", "#3 and #5 as 5:6", "#5 and #6 as 6:7", "#6 and #7 as 7:8", "#7 and #8 as 8:9", "#9 and #8 as 8:9" }

    Returns: {5, 10, 15, 20, 25, 24, 28, 32, 36, 32 }

  29. {"#0 and #1 as 9:8", "#1 and #2 as 9:9", "#0 and #3 as 9:9", "#3 and #4 as 7:8", "#0 and #5 as 8:9", "#6 and #5 as 5:7", "#5 and #7 as 8:3", "#7 and #8 as 9:9", "#7 and #9 as 8:9" }

    Returns: {32256, 28672, 28672, 32256, 36864, 36288, 25920, 13608, 13608, 15309 }

  30. {"#0 and #1 as 2:3", "#1 and #2 as 3:2" }

    Returns: {2, 3, 2 }

  31. {"#0 and #1 as 7:9", "#1 and #2 as 2:9", "#2 and #3 as 3:9", "#3 and #4 as 4:9", "#4 and #5 as 5:9", "#4 and #6 as 7:8", "#4 and #7 as 7:9", "#7 and #8 as 8:9", "#9 and #8 as 9:4" }

    Returns: {62720, 80640, 362880, 1088640, 2449440, 4408992, 2799360, 3149280, 3542940, 7971615 }

  32. {"#0 and #1 as 9:8", "#1 and #2 as 9:8", "#2 and #3 as 9:8", "#3 and #4 as 9:8", "#5 and #6 as 9:8", "#6 and #7 as 9:8", "#7 and #8 as 9:8", "#8 and #9 as 9:8", "#4 and #5 as 9:8" }

    Returns: {387420489, 344373768, 306110016, 272097792, 241864704, 214990848, 191102976, 169869312, 150994944, 134217728 }

  33. {"#0 and #1 as 8:9", "#1 and #2 as 8:9", "#2 and #3 as 8:9", "#3 and #4 as 8:9", "#4 and #5 as 8:9", "#5 and #6 as 8:9", "#6 and #7 as 8:9", "#7 and #8 as 8:9", "#8 and #9 as 8:9" }

    Returns: {134217728, 150994944, 169869312, 191102976, 214990848, 241864704, 272097792, 306110016, 344373768, 387420489 }

  34. {"#0 and #2 as 6:8", "#1 and #3 as 9:3", "#2 and #3 as 7:5" }

    Returns: {21, 60, 28, 20 }

  35. {"#0 and #1 as 8:9", "#1 and #2 as 8:9", "#2 and #3 as 8:9", "#3 and #4 as 8:9", "#4 and #5 as 8:9", "#5 and #6 as 8:9", "#6 and #7 as 8:9", "#7 and #8 as 8:9", "#8 and #9 as 7:9" }

    Returns: {117440512, 132120576, 148635648, 167215104, 188116992, 211631616, 238085568, 267846264, 301327047, 387420489 }

  36. {"#1 and #2 as 7:9", "#0 and #1 as 1:3" }

    Returns: {7, 21, 27 }

  37. {"#6 and #3 as 9:7", "#2 and #8 as 6:8", "#1 and #0 as 5:2", "#1 and #5 as 9:1", "#3 and #5 as 9:1", "#2 and #7 as 9:2", "#7 and #4 as 9:2", "#4 and #0 as 9:3" }

    Returns: {252, 630, 15309, 630, 756, 70, 810, 3402, 20412 }

  38. {"#0 and #1 as 1:9", "#1 and #2 as 1:9", "#2 and #3 as 1:9", "#3 and #4 as 1:9", "#4 and #5 as 1:9", "#5 and #6 as 1:9", "#6 and #7 as 1:9", "#7 and #8 as 1:9", "#8 and #9 as 1:9" }

    Returns: {1, 9, 81, 729, 6561, 59049, 531441, 4782969, 43046721, 387420489 }

  39. {"#0 and #3 as 1:2", "#1 and #2 as 2:1", "#2 and #3 as 2:1" }

    Returns: {1, 8, 4, 2 }

  40. {"#0 and #1 as 8:9", "#1 and #2 as 8:9", "#2 and #3 as 8:9", "#3 and #4 as 8:9", "#5 and #6 as 8:9", "#6 and #7 as 8:9", "#7 and #8 as 8:9", "#8 and #9 as 8:9", "#4 and #5 as 8:9" }

    Returns: {134217728, 150994944, 169869312, 191102976, 214990848, 241864704, 272097792, 306110016, 344373768, 387420489 }

  41. {"#8 and #9 as 2:1", "#0 and #1 as 3:7", "#7 and #6 as 5:2", "#4 and #3 as 7:9", "#5 and #4 as 9:8", "#0 and #8 as 8:3", "#2 and #3 as 6:5", "#9 and #2 as 4:7", "#5 and #6 as 3:9" }

    Returns: {18432, 43008, 6048, 5040, 3920, 4410, 13230, 33075, 6912, 3456 }

  42. {"#0 and #1 as 9:1", "#1 and #2 as 9:1", "#2 and #3 as 9:1", "#3 and #4 as 9:1", "#4 and #5 as 9:1", "#5 and #6 as 9:1", "#6 and #7 as 9:1", "#7 and #8 as 9:1", "#8 and #9 as 9:1" }

    Returns: {387420489, 43046721, 4782969, 531441, 59049, 6561, 729, 81, 9, 1 }

  43. {"#0 and #2 as 1:2", "#2 and #1 as 2:3", "#1 and #3 as 2:7", "#3 and #4 as 1:2", "#4 and #5 as 2:9" }

    Returns: {2, 6, 4, 21, 42, 189 }

  44. {"#0 and #1 as 9:3", "#9 and #8 as 9:5", "#2 and #3 as 9:7", "#5 and #4 as 9:1", "#6 and #7 as 9:8", "#1 and #8 as 9:8", "#3 and #4 as 9:7", "#1 and #3 as 5:8", "#5 and #7 as 7:8" }

    Returns: {945, 315, 648, 504, 392, 3528, 4536, 4032, 280, 504 }

  45. {"#0 and #1 as 3:2", "#2 and #1 as 9:7" }

    Returns: {21, 14, 18 }

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: