Coin Piles

Coin Piles
CSES medium

There are two coin piles with \(a\) and \(b\) coins. In one move, you remove either one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile.

Can you make both piles empty? Answer \(t\) such questions.

Constraints:

  • \(1 \le t \le 10^5\)
  • \(0 \le a, b \le 10^9\)

Input:

  • First line: integer \(t\) — the number of tests.
  • Next \(t\) lines: two integers \(a\) and \(b\).

Output:

  • For each test, one line: YES if both piles can be emptied, otherwise NO.

Example:

Input:

3
2 1
2 2
3 3

Output:

YES
NO
YES
Solution

Suppose we make \(x\) moves of the first kind (remove \(1\) from the left and \(2\) from the right) and \(y\) moves of the second kind (remove \(2\) from the left and \(1\) from the right). Both piles become empty exactly when

\[ x + 2y = a, \qquad 2x + y = b, \]

for some integers \(x, y \ge 0\). We find the conditions by case work on what can go wrong.

  • The total is not divisible by \(3\). Every move removes \(3\) coins, so \(a + b\) must be divisible by \(3\). Indeed, adding the two equations gives \(3(x + y) = a + b\).
  • One pile is too large. Every move removes at most twice as many coins from one pile as from the other. So we need \(a \le 2b\) and \(b \le 2a\). Indeed, solving the equations gives \(x = (2b - a) / 3\) and \(y = (2a - b) / 3\), and these must not be negative.

If both conditions hold, \(x\) and \(y\) are non-negative integers (\(2b - a = 2(a + b) - 3a\) is divisible by \(3\), and so is \(2a - b\)), so the answer is YES. Otherwise it is NO.

For \((2, 2)\) the total \(4\) is not divisible by \(3\). For \((3, 3)\) we get \(x = y = 1\).

\(a + b\) and \(2a\) can be up to \(2 \cdot 10^9\), which does not fit in int, so we read \(a\) and \(b\) as long long.

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        long long a, b;
        cin >> a >> b;

        // every move removes 3 coins, and neither pile may be more than twice the other
        if ((a + b) % 3 == 0 && a <= 2 * b && b <= 2 * a) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}