Sequence Construction
플래티넘 IV의견: 0
Lately, the cows on Farmer John's farm have been infatuated with watching the
show Apothecowry Dairies. The show revolves around a clever bovine sleuth CowCow
solving problems of various kinds. Bessie found a new problem from the show, but
the solution won't be revealed until the next episode in a week! Please solve
the problem for her.
You are given integers \(M\) and \(K\) \((1 \leq M \leq 10 ^ 9, 1 \leq K \leq 31)\).
Please choose a positive integer \(N\) and construct a sequence \(a\) of \(N\)
non-negative integers such that the following conditions are satisfied:
- \(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\)
If no such sequence exists, print \(-1\).
\(\dagger \text{ popcount}(x)\) is the number of bits equal to \(1\) in the binary
representation of the integer \(x\). For instance, the popcount of \(11\) is \(3\) and
the popcount of \(16\) is \(1\).
\(\dagger \oplus\) is the bitwise xor operator.
The input will consist of \(T\) (\(1 \le T \le 5 \cdot 10^3\)) independent test
cases.
Problem credits: Aakash Gokhale
SCORING
- Input 2: \(M \leq 8, K \leq 8\)
- Inputs 3-5: \(M > 2^K\)
- Inputs 6-18: No additional constraints.
Problem credits: Aakash Gokhale
The first line contains \(T\).
The first and only line of each test case has \(M\) and \(K\).
It is guaranteed that all test cases are unique.
Output the solutions for \(T\) test cases as follows:
If no answer exists, the only line for that test case should be \(-1\).
Otherwise, the first line for that test case should be a single integer \(N\), the
length of the sequence -- (\(1 \le N \le 100\)).
The second line for that test case should contain \(N\) space-separated integers
that satisfy the conditions -- (\(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
평가 및 의견
Sequence Construction
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Sequence Construction