coin-piles

Coin Piles

CSES medium

توجد كومتان من العملات فيهما \(a\) و \(b\) عملة. في كل حركة تزيل إما عملة واحدة من الكومة اليسرى وعملتين من الكومة اليمنى، أو عملتين من الكومة اليسرى وعملة واحدة من الكومة اليمنى.

هل يمكنك أن تجعل الكومتين فارغتين؟ أجب عن \(t\) سؤالًا من هذا النوع.

القيود:

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

الإدخال:

السطر الأول: عدد صحيح \(t\) — عدد الاختبارات.
الأسطر الـ \(t\) التالية: عددان صحيحان \(a\) و \(b\).

المخرجات:

لكل اختبار، سطر واحد: YES إذا أمكن إفراغ الكومتين، وإلا NO.

مثال:

الإدخال:

المخرجات:

YES
NO
YES

الحل

لنفرض أننا نجري \(x\) حركة من النوع الأول (نزيل \(1\) من اليسرى و \(2\) من اليمنى) و \(y\) حركة من النوع الثاني (نزيل \(2\) من اليسرى و \(1\) من اليمنى). تصبح الكومتان فارغتين بالضبط عندما

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

لعددين صحيحين \(x, y \ge 0\). نجد الشروط بالعمل على الحالات التي قد يفشل فيها ذلك.

المجموع لا يقبل القسمة على \(3\). كل حركة تزيل \(3\) عملات، لذلك يجب أن يقبل \(a + b\) القسمة على \(3\). فعلًا، جمع المعادلتين يعطي \(3(x + y) = a + b\).
إحدى الكومتين كبيرة جدًا. كل حركة تزيل من إحدى الكومتين على الأكثر ضعف ما تزيله من الأخرى. لذلك نحتاج \(a \le 2b\) و \(b \le 2a\). فعلًا، حل المعادلتين يعطي \(x = (2b - a) / 3\) و \(y = (2a - b) / 3\)، ويجب ألا يكونا سالبين.

إذا تحقق الشرطان، يكون \(x\) و \(y\) عددين صحيحين غير سالبين (\(2b - a = 2(a + b) - 3a\) يقبل القسمة على \(3\)، وكذلك \(2a - b\))، فالجواب YES. وإلا فالجواب NO.

للزوج \((2, 2)\) المجموع \(4\) لا يقبل القسمة على \(3\). للزوج \((3, 3)\) نحصل على \(x = y = 1\).

قد يصل \(a + b\) و \(2a\) إلى \(2 \cdot 10^9\)، وهذا لا يتسع في int، لذلك نقرأ \(a\) و \(b\) بالنوع 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";
        }
    }
}