Editorial for TLE '16 Contest 1 P1 - Buying Paper


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ZQFMGB12

This is a relatively straightforward problem.

Find the maximum and minimum weighted coin for both the quarters and dimes. This can be done using iteration or a sort.

As the problem states, the value of a coin is the number of cents it is worth divided by its weight. Thus, the value of a dime is 10 divided by its mass, and the value of a quarter is 25 divided by its mass. To answer the question, compare the value of the heaviest dime (least valued dime) with the lightest quarter (most valued quarter) to see if all dimes are better. If this is not true, compare the value of the heaviest quarter (least valued quarter) with the lightest dime (most valued dime) to see if all quarters are better. If neither of these conditions are true, no coin is better than the other.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.