페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8415

Sequence Construction 1s 1024MB

문제

최근, 소들이 즐겨보는 TV쇼 "Apothecowry Dairies"의 한 에피소드에서 명탐정 소 CowCow가 여러 가지 문제를 해결하는 모습을 보고 있던 소 Bessie는, 다음 주에 공개될 에피소드까지 기다릴 수 없어서 문제를 직접 풀어보기로 했습니다.

문제는 다음과 같습니다.

정수 M과 K가 주어집니다 (1 \le M \le 10^9,\ 1 \le K \le 31). 여러분은 양의 정수 N (1 \le N \le 100)을 선택하고, N개의 비음수 정수 a_1, a_2, \dots, a_N로 구성된 수열 a를 다음 조건을 만족하도록 구성해야 합니다.

a_1 + a_2 + \dots + a_N = M.

\text{popcount}(a_1) \oplus \text{popcount}(a_2) \oplus \dots \oplus \text{popcount}(a_N) = K.

여기서 \text{popcount}(x)는 정수 x의 이진수 표현에서 1의 개수를 의미하며 (예: \text{popcount}(11)=3,\ \text{popcount}(16)=1), \oplus는 bitwise XOR 연산자입니다.

만약 위 조건을 만족하는 수열이 존재하지 않으면, -1을 출력하세요.


입력

첫 번째 줄에 테스트 케이스의 수 T (1 \le T \le 5\cdot10^3)가 주어집니다.

각 테스트 케이스는 한 줄에 두 정수 M과 K가 공백으로 구분되어 주어집니다.


출력

각 테스트 케이스에 대해, 조건을 만족하는 수열이 존재하면 첫 번째 줄에 선택한 수열의 길이 N (1 \le N \le 100)을 출력하고, 두 번째 줄에 N개의 정수 a_1, a_2, \dots, a_N (0 \le a_i \le M)를 공백으로 구분하여 출력합니다.

만약 조건을 만족하는 수열이 존재하지 않으면, 해당 테스트 케이스에 대해 단 한 줄에 -1을 출력합니다.


예제 

3
2 1
33 5
10 5
2
2 0
3
3 23 7
-1

  • 첫 번째 테스트 케이스: M = 2, K = 1.
    수열 a = [2, 0]는 합이 2이며, \text{popcount}(2)=1 (이진수 10은 1의 비트가 1개), \text{popcount}(0)=0; 따라서 1 \oplus 0 = 1

  • 두 번째 테스트 케이스: M = 33, K = 5.
    수열 a = [3, 23, 7]는 합이 33이며, \text{popcount}(3)=2, \text{popcount}(23)=4, \text{popcount}(7)=3; 2 \oplus 4 \oplus 3 = 5.

  • 세 번째 테스트 케이스: M = 10, K = 5
    이러한 조건을 만족하는 수열이 존재하지 않으므로 -1을 출력합니다.


출처

USACO 2025 US Open Silver
로그인해야 코드를 작성할 수 있어요.