문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

예제1 - 입력

10 15 35

예제1 - 출력

1

예제2 - 입력

1 1 2

예제2 - 출력

0

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int a, b, c, sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        sum = a + b + c;
        System.out.println(bfs() ? 1 : 0);

    }
    static boolean bfs() {
        if (sum % 3 != 0) {
            return false;
        }

        Queue<Stones> queue = new LinkedList<>();
        Stones now = new Stones(a, b, c);
        boolean[][] visited = new boolean[sum + 1][sum + 1];

        queue.offer(now);
        visited[a][b] = true;
        while (!queue.isEmpty()) {
            now = queue.poll();

            int a = now.a;
            int b = now.b;
            int c = now.c;
            if ((a == b) && (b == c))
                return true;

            if (a != b) {
                int ta = a < b ? 2 * a : a - b;
                int tb = b < a ? 2 * b : b - a;

                if (!visited[ta][tb]) {
                    visited[ta][tb] = true;
                    queue.offer(new Stones(ta, tb, c));
                }
            }
            if (a != c) {
                int ta = a < c ? 2 * a : a - c;
                int tc = c < a ? 2 * c : c - a;

                if (!visited[ta][tc]) {
                    visited[ta][tc] = true;
                    queue.offer(new Stones(ta, b, tc));
                }
            }
            if (b != c) {
                int tb = b < c ? 2 * b : b - c;
                int tc = c < b ? 2 * c : c - b;

                if (!visited[tb][tc]) {
                    visited[tb][tc] = true;
                    queue.offer(new Stones(a, tb, tc));
                }
            }
        }
        return false;
    }
    static class Stones {
        public int a;
        public int b;
        public int c;
        public Stones(int a, int b, int c){
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
}