CSES 1. Coin Piles (1754)

출처:https://cses.fi/problemset/task/1754

---

문제 설명

You have two coin piles containing a and b coins. On each move, you can either remove 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.

Your task is to efficiently find out if you can empty both the piles.

입력

The first input line has an integer t: the number of tests.

After this, there are t lines, each of which has two integers a and b: the numbers of coins in the piles.

출력

For each test, print "YES" if you can empty the piles and "NO" otherwise.

입력 예

3
2 1
2 2
3 3

출력 예

YES
NO
YES

제약조건

• 1 <= t <= 10^5
• 0 <= a,b <= 10^9

---

문제 풀이

두개의 입력 a, b를 이용해서 가능한 조건들을 검사한다.

먼저, 한번에 제거 가능한 숫자는 3개 이므로, 두개의 합이 3의 배수가 아니면 불가능하다. 왼쪽에서 2개 제거하는 수를 x, 오른쪽에서 2개 제거하는 수를 y로 해서 계산한다.

더할 수는 없으므로 하나라도 음수이면 불가능하다. (x < 0 || y <0)

한쪽의 입력이 다른 쪽의 2배보다 크면 불가능하다. (a > 2b || 2a < b)

두 입력의 차가 abs(a-b) = abs(x-y) 이면, 모두 없애는게 가능하므로, 이 조건까지 확인해서 결과를 출력한다.  

프로그램 내용

#define MAX_T 100000
#define MAX_P 1000000000

int main()
{
    int a, b;
    int x, y;

	cin >> a >> b;
	x = (2*a-1*b)/3;
	y = (2*b-1*a)/3;

	if ((a+b) % 3 == 0)
		if ( a > 2*b || 2*a < b )
			cout << "NO" << endl;
		else if ( x < 0 || y < 0)
			cout << "NO" << endl;
		else if ( abs(a-b) == abs(x-y) )
        	cout << "YES" << endl;

        else
            cout << "NO" << endl;
    }
}

 

Introductory problems ( link )