방정식

면접 대비

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

요약

N개의 정수와 상한 M이 주어질 때, 각 A_i와 k의 XOR 값을 모두 더한 합이 M 이하가 되는 가장 큰 k를 구합니다. 그런 k가 없으면 -1을 출력합니다.

난이도: 보통10점 중 5점
유형: 비트 연산, 그리디
정답자: 아직 제출이 없습니다

문제

우주의 법칙은 음이 아닌 정수 N개로 된 배열로 표현할 수 있다. i번째 정수는 A_i이다.

음이 아닌 정수 k가 존재해서 다음 식을 만족하면 우주가 좋다고 한다: $(A_1 \oplus k) + (A_2 \oplus k) + \cdots + (A_N \oplus k) \le M$ . 여기서 $\oplus$ 는 비트 단위 배타적 논리합(bitwise exclusive or)을 뜻한다.

우주가 좋은 상태가 되는 k의 최댓값은 얼마인가?

입력

첫 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 N과 M이 주어지며, 각각 배열 A의 원소 개수와 식의 상한이다.

둘째 줄에는 N개의 정수가 주어지며, i번째 정수는 A_i이다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 우주가 좋은 상태가 되는 k의 최댓값이다. 그런 k가 없으면 -1을 출력한다.

제한

1 ≤ T ≤ 100.
1 ≤ N ≤ 1000.

힌트

샘플 케이스 #1에서 배열의 원소는 N = 3개이고 M = 27이다. 우주를 좋게 만드는 k의 최댓값은 12이며, (8 xor 12) + (2 xor 12) + (4 xor 12) = 26이다.

샘플 케이스 #2에서 배열의 원소는 N = 4개이고 M = 45이다. 우주를 좋게 만드는 k의 최댓값은 14이며, (30 xor 14) + (0 xor 14) + (4 xor 14) + (11 xor 14) = 45이다.

샘플 케이스 #3에서 배열의 원소는 N = 1개이고 M = 0이다. 우주를 좋게 만드는 k의 최댓값은 100이며, 100 xor 100 = 0이다.

샘플 케이스 #4에서는 우주를 좋게 만드는 k가 없으므로 답은 -1이다.

예제1

예제 1

입력

4
3 27
8 2 4
4 45
30 0 4 11
1 0
100
6 2
5 5 1 5 1 0

예상 출력

Case #1: 12
Case #2: 14
Case #3: 100
Case #4: -1