Editorial for ICPC NAQ 2016 K - Robotopia

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.
  • We're looking for positive integers x, y such that: \displaystyle \begin{align*}l_1 x + l_2 y &= l_t \\ a_1 x + a_2 y &= a_t\end{align*}
  • This is a system of linear equations, but we want integer solutions.
  • The constraints are small enough that complete search works:
    • Loop through all values x = 1, 2, \dots while l_1 x < l_t.
    • Solve for the other variable: y = (l_t - l_1 x)/l_2.
    • Check if x, y are positive integers that satisfy the system of equations.
  • Output ? if zero or multiple solutions were found.

Comments

There are no comments at the moment.