레이팅 미적용최근 농부 존의 농장에 사는 소들은 Apothecowry Dairies라는 드라마 시청에 푹 빠져 있다. 이 드라마는 영리한 소 탐정 카우카우가 온갖 종류의 문제를 해결하는 이야기다. 베시는 드라마에서 새로운 문제를 발견했지만, 해답은 일주일 뒤 다음 화에서야 공개된다! 베시를 위해 문제를 풀어 주자.
정수 \(M\)과 \(K\)(\(1 \leq M \leq 10 ^ 9, 1 \leq K \leq 31\))가 주어진다. 양의 정수 \(N\)을 선택하고, 다음 조건을 만족하는 음이 아닌 정수 \(N\)개의 수열 \(a\)를 구성하시오.
- \(1 \le N \le 100\)
- \(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\)
그러한 수열이 존재하지 않으면 \(-1\)을 출력한다.
\(\dagger \text{ popcount}(x)\)는 정수 \(x\)의 이진 표현에서 \(1\)인 비트의 개수이다. 예를 들어 \(11\)의 popcount는 \(3\)이고 \(16\)의 popcount는 \(1\)이다.
\(\dagger \oplus\)는 비트 단위 xor 연산자이다.
입력은 \(T\)개(\(1 \le T \le 5 \cdot 10^3\))의 독립적인 테스트 케이스로 이루어진다.
Problem credits: Aakash Gokhale
배점
- 입력 2: \(M \leq 8, K \leq 8\)
- 입력 3-5: \(M > 2^K\)
- 입력 6-18: 추가 제약이 없다.
Problem credits: Aakash Gokhale
첫째 줄에 \(T\)가 주어진다.
각 테스트 케이스의 첫째 줄이자 유일한 줄에 \(M\)과 \(K\)가 주어진다.
모든 테스트 케이스가 서로 다름이 보장된다.
\(T\)개의 테스트 케이스에 대한 해를 다음과 같이 출력한다.
답이 존재하지 않으면 해당 테스트 케이스의 유일한 줄은 \(-1\)이어야 한다.
그렇지 않으면 해당 테스트 케이스의 첫째 줄은 수열의 길이인 정수 \(N\)(\(1 \le N \le 100\))이어야 한다.
해당 테스트 케이스의 둘째 줄은 조건을 만족하는, 공백으로 구분된 정수 \(N\)개(\(0 \le a_i \le M\))를 포함해야 한다.
3
2 1
33 5
10 52
2 0
3
3 23 7
-1In the first test case, the elements in the array \(a = [2, 0]\) sum to \(2\). The
xor sum of popcounts is \(1 \oplus 0 = 1\). Thus, all the conditions are
satisfied.
In the second test case, the elements in the array \(a = [3, 23, 7]\) sum to \(33\).
The xor sum of the popcounts is \(2 \oplus 4 \oplus 3 = 5\). Thus, all conditions
are satisfied.
Other valid arrays are \(a = [4, 2, 15, 5, 7]\) and \(a = [1, 4, 0, 27, 1]\).
It can be shown that no valid arrays exist for the third test case.
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > US Open > Silver