[C++] 33616번 판드랄추

https://www.acmicpc.net/problem/33616

---

 

25/09/30

 

 

XOR의 성질을 이용한 재미있는 애드혹 문제다.

---

 

문제 접근 방식:

 

 

문제를 요약하면, 두 수 $A, B$가 주어지는데, 하나의 수에는 XOR연산을, 하나의 수에는 덧셈 연산을 동시에 진행한다.

 

이 과정을 반복하여 두 수를 같게 만들 수 있는지의 여부를 묻고, 만약 같게 만들 수 있다면 최소 연산 수가 소요되는 방법을 출력하는 문제이다.

 

 

여기서 관찰할 점들을 꼽아보면 다음과 같다.

 

1. 어떤 수에 덧셈 연산을 하면 항상 늘어난다.

 

2. 어떤 수에 XOR연산을 하면 덧셈 연산한 것 보다 더 커지게 늘어날 수는 없다. 오히려 줄어들 수도 있다.

 

 

일단 이 두 가지를 관찰하면, 다음과 같은 결론을 얻을 수 있다.

 

어떤 두 수의 차이가 $N$이면, 한쪽은 XOR연산을, 한쪽은 덧셈 연산을 해서 어떤 두 수의 차이를 점점 줄여나갈 수 있겠구나!

 

어떤 두 수의 차이가 $0$이 된다면 두 수를 같게 만들 수 있다는 뜻이다.

 

 

이게 불가능한 경우를 생각해보자.

 

예제 입력을 통해 약간 유추를 해볼 수 있는데, 어떤 두 수의 차이가 $1$일때 불가능 함을 볼 수 있다.

 

실제로는 어떤 두 수의 차이가 홀수인 경우 항상 불가능 한데, 이에 대한 증명은 다음과 같다.

 

증명)
$|a - b|$가 홀수라고 하자.

일반성을 잃지 않고, $a < b$라고 가정하자.
이때, $a$의 lsb가 $0$이라면 $b$의 lsb는 $1$이고, $a$의 lsb가 $1$이라면 $b$의 lsb는 $0$이다.

일반성을 잃지 않고, $a$의 lsb가 $0$, $b$의 lsb가 $1$이라고 하자.

이때 $a$에 홀수를 XOR하고 $b$에 홀수를 더하면 $a$의 lsb는 $1$, $b$의 lsb는 $0$이 된다.
마찬가지로 $a$에 홀수를 더하고 $b$에 홀수를 XOR하면, $a$의 lsb는 $1$, $b$의 lsb는 $0$이 된다.
$a$에 짝수를 XOR하고 $b$에 짝수를 더한다면 $a$와 $b$의 lsb는 서로 변하지 않는다.
$a$에 짝수를 더하고 $b$에 짝수를 XOR하면 $a$와 $b$의 lsb는 서로 변하지 않는다.

즉, 모든 경우에 대해서 어떤 연산을 진행하든 $a$와 $b$의 lsb가 항상 다르기 때문에 홀수인 경우에는 두 수를 같게 만들 수 없다.

 

어떤 두 수의 차이가 짝수인 경우라면, XOR의 성질에 의해 적어도 $2$번만에 만들 수 있음은 쉽게 관찰할 수 있다.

 

작은 쪽에 두 수의 차이의 절반을 $2$번 더해주고, 큰 쪽에 두수의 차이의 절반을 $2$번 XOR해주면, XOR을 두번한 쪽은 그대로지만 덧셈을 두번한 쪽은 큰 쪽과 같아지기 때문이다.

 

실제로는 $1$번으로도 가능한 경우가 생기는데, 위의 똑같은 과정(큰쪽에 두 수 차이의 절반을 XOR, 작은쪽에 같은 수를 덧셈)을 거쳤는데 같아지면 $1$번으로도 가능하다.

 

이를 그대로 구현하면 된다. 이때, 수의 범위가 int범위를 초과하기 때문에 long long범위로 연산해야함에 유의하자.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 33616번 판드랄추
// 애드혹
#include <iostream>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

int main(void){
    fastio;

    int T; cin >> T;
    while (T--){
        long long a, b; cin >> a >> b;
        long long d = abs(a-b);
        if (d & 1LL){
            cout << -1 << endl;
        } else {
            long long half = d/(2LL);
            if (a > b){
                if ((a ^ half) == (b + half)){
                    cout << 1 << endl << 'A' << ' ' << half << endl;
                } else {
                    cout << 2 << endl << 'A' << ' ' << half << endl << 'A' << ' ' << half << endl;
                }
            } else {
                if ((b ^ half) == (a + half)){
                    cout << 1 << endl << 'B' << ' ' << half << endl;
                } else {
                    cout << 2 << endl << 'B' << ' ' << half << endl << 'B' << ' ' << half << endl;
                }
            }
        }
    }
    return 0;
}