Elevanagram

시간 제한20초메모리 제한1024 MB

요약

1부터 9까지 각 숫자의 개수가 주어질 때, 자릿수가 정해진 두 위치 집합의 합 차이가 11의 배수가 되도록 숫자를 나눌 수 있는지 판정한다.

문제

어떤 수가 11의 배수일 필요충분조건은 각 자릿수의 교대합이 11에 대해 0과 합동인 것이다. 예를 들어 8174958은 8 - 1 + 7 - 4 + 9 - 5 + 8 = 22이므로 11의 배수이다.

1부터 9까지의 숫자로 이루어진 수가 주어질 때, 자릿수를 재배열해서 11의 배수를 만들 수 있는가?

수는 매우 클 수 있으므로, 정수 A1, A2, ..., A9가 주어진다. 모든 i에 대해 숫자 i는 Ai개 있다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 아홉 개의 정수 A1, A2, ..., A9가 주어진다.

각 테스트 케이스에 대해 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 자릿수를 재배열해서 11의 배수를 만들 수 있으면 YES, 아니면 NO이다.

샘플 케이스 #1에서 자릿수는 336이고, 363으로 재배열할 수 있다. 3 - 6 + 3 = 0이므로 11의 배수이다.
샘플 케이스 #2에서 자릿수는 999999999999이고, 9 - 9 + 9 - 9 + ... - 9 = 0이므로 이미 11의 배수이다.
샘플 케이스 #3에서 자릿수는 5578이고, 어떻게 재배열해도 11의 배수를 만들 수 없다.
샘플 케이스 #4에서 자릿수는 111234이고, 142131로 재배열할 수 있다. 1 - 4 + 2 - 1 + 3 - 1 = 0이므로 11의 배수이다.
샘플 케이스 #5에서 자릿수는 11177799이고, 19191777로 재배열할 수 있다. 1 - 9 + 1 - 9 + 1 - 7 + 7 - 7 = -22이고, 이는 11에 대해 0과 합동이다.
샘플 케이스 #6에서 자릿수는 8 하나뿐이고, 어떻게 재배열해도 11의 배수를 만들 수 없다.

예제 1

입력

6
0 0 2 0 0 1 0 0 0
0 0 0 0 0 0 0 0 12
0 0 0 0 2 0 1 1 0
3 1 1 1 0 0 0 0 0
3 0 0 0 0 0 3 0 2
0 0 0 0 0 0 0 1 0

예상 출력

Case #1: YES
Case #2: YES
Case #3: NO
Case #4: YES
Case #5: YES
Case #6: NO