IngredientProportions

SRM 429 · 2008-12-11 · by darnley

SRM 429 · 2008-12-11 · by darnley · Graph Theory, Simple Math, String Parsing

Show categories

Class Name: IngredientProportions

Return Type: int[]

Method Name: getMasses

Arg Types: (vector<string>)

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 # as :<q>" (quotes for clarity), which means that the mass of ingredient <a> divided by the mass of ingredient in the cocktail must be equal to /<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.

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 will be between 0 and N-1, inclusive.
Each 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

{"#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.

{"#0 and #1 as 9:8","#1 and #2 as 9:8"}
Returns: {81, 72, 64 }

{"#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.

{"#2 and #3 as 6:8", "#0 and #1 as 9:3", "#3 and #0 as 7:5"}
Returns: {60, 20, 63, 84 }

{"#0 and #1 as 9:9"}
Returns: {1, 1 }

Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class IngredientProportions with a public method vector<int> getMasses(vector<string> proportions) · 45 test cases · 2 s / 256 MB per case