SRM 697, D2, 250-Pointer (TriangleMaking)

James S. Plank

Sun Aug 28 14:14:17 EDT 2016
Example 0 summarizes the whole problem -- if the sum of the two shorter sides is less than or equal to the longest side, then you can't make a triangle. In that case, you must shorten the longest side so that it is one unit less than the sum of the other two.

If the sum of the two shorter sides is greater than the longest side, then you don't need to do any shortening.

So, the challenge here is to identify the sides as "two shortest" and "longest." The answer to doing this quickly and reliably is to use sorting. What I did was put all three sides into a vector, and then use the sort() method from algorithms to sort it. Now, it's easy to identify the two shorter sides, and the longest one. This works even when the length of the sides are not unique (as in example 1).

You can use a multiset or multimap to do the sorting, too, although I think that the vector is easier. What you don't want to do is put in a bunch of if statements to try to identify the longest side and shortest sides. That is a bug-prone exercise.


My Solution.