Notice that after performing $$$z$$$ operations, the robot's $$$x$$$-coordinate will be exactly $$$z$$$, while its $$$y$$$-coordinate cannot exceed $$$z$$$.

We will first consider the case $$$b\le a$$$, then handle the special case $$$b=a+1$$$.

Notice that the robot can reach any point $$$(x,y)$$$ where $$$0\le y\le x$$$ and $$$x$$$ and $$$y$$$ have the same parity in exactly $$$x$$$ operations. To do so, we can first move up until reaching $$$y$$$, then alternate between moving up and down.

But what if $$$x$$$ and $$$y$$$ have different parities?

In this case, we can reach $$$(x,y-1)$$$ in exactly $$$x$$$ operations, since $$$x$$$ and $$$y-1$$$ have the same parity.

Now, recall that in each operation, the robot moves vertically before moving horizontally. Therefore, we can perform one additional operation:

The robot visits $$$(x,y)$$$ during this operation, so the answer is $$$x+1$$$.

Now, let's consider the remaining cases:

• If $$$b=a+1$$$, we can use the same construction, since $$$a$$$ and $$$b$$$ have different parities. We reach $$$(a,b-1)=(a,a)$$$ in $$$a$$$ operations, then visit $$$(a,b)$$$ during the next operation. Thus, the answer is $$$a+1$$$.
• If $$$b \gt a+1$$$, reaching $$$(a,b)$$$ is impossible, since the robot can make at most $$$a+1$$$ vertical moves before leaving column $$$a$$$.

Therefore, the answer is:

• $$$-1$$$ if $$$b \gt a+1$$$.
• $$$a$$$ if $$$a$$$ and $$$b$$$ have the same parity.
• $$$a+1$$$ otherwise.

The time complexity is $$$O(1)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int a, b;
    cin >> a >> b;
    if (b > a + 1) cout << -1 << '\n';
    else if (a % 2 == b % 2) cout << a << '\n';
    else cout << a + 1 << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve