Editorial for COCI '15 Contest 3 #4 Slon
Submitting an official solution before solving the problem yourself is a bannable offence.
The condition from the task is that the expression is a first degree polynomial of the form . Let
. If we calculate the expression at
, we will see that
. If we calculate it at
, we will see that
. This gives us values
and
. We are left to figure out how to calculate the minimal value of
such that
. Given that
, we can iterate over all values of
until we find the minimal value that satisfies the upper equation. We are left to figure out how to calculate the expression at
and
.
One of the ways we can do this is using the command Another way is to parse the expression from infix to postfix notation using the "shunting-yard" algorithm. Another approach is to convert the expression to postfix notation and then the addition, multiplication and subtraction is performed over polynomials with maximal degree of eval
in Python. and, finally, the same equation of the form
is solved.
Comments