Editorial for ICPC NAQ 2016 K - Robotopia - DMOJ: Modern Online Judge

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$ $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*}$ $\begin{aligned} l_{1} x + l_{2} y & = l_{t} \\ a_{1} x + a_{2} y & = a_{t} \end{aligned}$
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$ $x = 1, 2, \dots$ while $l_1 x < l_t$ $l_{1} x < l_{t}$ .
- Solve for the other variable: $y = (l_t - l_1 x)/l_2$ $y = (l_{t} - l_{1} x) / l_{2}$ .
- Check if $x, y$ $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.