All Things Being Equal

From programming_contest
Jump to navigation Jump to search

Balances have a delightful property that assuming the bars are massless, you can calculate the ratio of any individual pan to the total weight of the balance by starting at the top and dividing recursively.

For instance, assuming a normalized balance weight of 1, and each bar hung exactly in the middle, the weight of the two highest "sub" balances must be 1/2, and then 1/4...etc. If the bars are not hung in the middle, it just changes the divide factor slightly...in the ratio of the length of the bar. Fortunately THAT is not the case here, but we DO have weights on the bars. So to deal with that, we just distribute those weights equally to the sub-balances, and then recursively down to individual weights. If there is a known weight, simply add it, otherwise make note that it needs to be added to the unknown.

Once this is done, there are a couple cases

  1. there is a known weight. We have the fraction of the total weight of the balance this weight must be, so calculate the balance weight.
  2. there are NO known weights. Choose two unknown weights that have the same variable but different fractions of the total mass and solve for the weight of the balance (again being sure to include the divided mass of the bars as well)
  3. there are no known weights, and no pairs of single variables that match
    1. If they are all different variables, the solution is MANY
    2. If there are similar variables, but the multipliers and added factors from the bar are the same, the solution is MANY
    3. If there are similar variables, but the multipliers are the same, and the added factors are different, the answer is NONE

Now we have the total mass balance, so at this point we can go pan by pan and either

  1. check whether the known weight is consistent with what it should be
  2. calculate the unknown weight that should go there, ensuring similar unknown weights are consistent