Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Think of every set bit as a token sitting at its bit position. When a carry happens, two tokens at the same bit merge into one token one bit higher.
For one move with c carries, popcount changes by +1-c: you insert one token, then each carry merge removes one token. So c = 1 + popcount(before) - popcount(after).
After all k moves, the total score is k + popcount(n) - popcount(final). So the whole problem is secretly: make the final popcount as small as possible.
Look only at the original set bits of n. If several of them end up merged into one final bit, they must be consecutive in bit order. A carry cannot jump over an original 1 and politely ignore it. Binary is not that chill.
For a consecutive block of original set bits with sum S, making it become one final bit 2^h costs popcount(2^h - S) added powers. Precompute those block costs, then DP over blocks and used cost. If the minimum final token count is q, the answer is k + popcount(n) - q.
The Popcount Identity
Forget the move order for a second and count tokens.
A set bit is one token. Adding inserts one new token at bit . If there is no carry, token count goes up by . If there are carries, every carry merges two equal-position tokens into one token one bit higher, so every carry decreases the token count by .
So for one move with c carries,
.
Rearrange it:
.
Sum over all k moves and everything telescopes:
.
So maximizing carries is exactly the same as minimizing the final popcount. That is the main trick. The carries are just binary accounting, not magic.
What Final Numbers Can We Build?
Suppose the original set bits of n are at positions
,
where .
If some original set bits merge into one final bit, they must form a consecutive block in this list. Why? Because carrying only moves upward. If a lower group sends a carry through the position of the next original 1, then that 1 gets involved too. You cannot skip it. That false assumption is where greedy solutions go to die.
Now take one consecutive block i..j. Let
.
If this whole block becomes one final token at bit h, then its final value is , so we must add
.
The fewest moves needed to add exactly that value is popcount(2^h - S), because each move contributes one power of two.
There is one boundary rule: if j + 1 exists, then this block's final bit must be below b[j+1]. Otherwise it would collide with the next original set bit, meaning the next bit should have been in the same block. So:
h < b[j+1];h can be higher freely.Therefore define:
cost[i][j] = min popcount(2^h - S)
over all valid h.
Why At Most k Moves Is Enough
The DP will find a way using at most k powers. The actual game needs exactly k moves, so we need to not hand-wave this part.
A number M can be written as exactly k powers of two iff:
popcount(M) <= k, andM >= k.The first condition is the minimum number of powers. The second condition is because every move adds at least 1. You can split powers, like , until you get any term count up to M.
If our construction uses c <= k added powers and its added value is already at least k, great.
If the added value is still less than k, then c < k. Take the highest final token and raise it by d = k - c more bit positions. This preserves the number of final tokens. It increases the addend's popcount by exactly d, because it adds a clean string of 1 bits above the old target. The added value also increases by at least d, so now the value is at least k and the popcount is at most k.
So minimizing final popcount with at most k added powers is enough. Nice little loophole, but legal.
DP
Let p = popcount(n). If k >= 60, the answer is immediate: we can make the final number a single power of two, for example . Since n < 2^30, the difference has at most 60 set bits and is huge enough to split into exactly k moves. Thus the minimum final popcount is 1.
For k < 60, do the block DP.
Precompute cost[i][j] for every consecutive block of set bits. Since k < 60 and n < 2^30, scanning target bits up to about 95 is plenty. If a target that high still has cost at most k, it would already have shown up before then.
Then:
dp[x][used] = minimum number of final tokens after processing the first x original set bits using used added powers.
Transition:
Choose the next block x..j, pay cost[x][j], and add one final token.
The best final token count is
q = min dp[p][used] for used <= k.
Finally:
answer = k + popcount(n) - q.
That is the whole thing: turn carry chaos into popcount minimization, then partition the original set bits into mergeable chunks.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int pop128(unsigned __int128 x) {
int res = 0;
while (x > 0) {
res += int(x & 1);
x >>= 1;
}
return res;
}
int main() {
setIO();
int tc;
cin >> tc;
while (tc--) {
ll n, k;
cin >> n >> k;
vector<int> bit;
for (int i = 0; i < 30; i++) {
if ((n >> i) & 1LL) bit.push_back(i);
}
int p = int(bit.size());
if (k == 0) {
cout << 0 << '\n';
continue;
}
if (k >= 60) {
cout << k + p - 1 << '\n';
continue;
}
int K = int(k);
const int INF = 1e9;
const int LIM = 95;
vector<unsigned __int128> pref(p + 1, 0);
for (int i = 0; i < p; i++) {
pref[i + 1] = pref[i] + (((unsigned __int128)1) << bit[i]);
}
vector<vector<int>> cost(p, vector<int>(p, INF));
for (int i = 0; i < p; i++) {
for (int j = i; j < p; j++) {
unsigned __int128 sum = pref[j + 1] - pref[i];
int hi = (j + 1 < p ? bit[j + 1] - 1 : LIM);
for (int h = bit[j]; h <= hi; h++) {
unsigned __int128 target = ((unsigned __int128)1) << h;
if (target < sum) continue;
cost[i][j] = min(cost[i][j], pop128(target - sum));
}
}
}
vector<vector<int>> dp(p + 1, vector<int>(K + 1, INF));
dp[0][0] = 0;
for (int i = 0; i < p; i++) {
for (int used = 0; used <= K; used++) {
if (dp[i][used] == INF) continue;
for (int j = i; j < p; j++) {
int c = cost[i][j];
if (c == INF || used + c > K) continue;
dp[j + 1][used + c] = min(dp[j + 1][used + c], dp[i][used] + 1);
}
}
}
int q = INF;
for (int used = 0; used <= K; used++) {
q = min(q, dp[p][used]);
}
cout << k + p - q << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int pop128(unsigned __int128 x) {
int res = 0;
while (x > 0) {
res += int(x & 1);
x >>= 1;
}
return res;
}
int main() {
setIO();
int tc;
cin >> tc;
while (tc--) {
ll n, k;
cin >> n >> k;
vector<int> bit;
for (int i = 0; i < 30; i++) {
if ((n >> i) & 1LL) bit.push_back(i);
}
int p = int(bit.size());
if (k == 0) {
cout << 0 << '\n';
continue;
}
if (k >= 60) {
cout << k + p - 1 << '\n';
continue;
}
int K = int(k);
const int INF = 1e9;
const int LIM = 95;
vector<unsigned __int128> pref(p + 1, 0);
for (int i = 0; i < p; i++) {
pref[i + 1] = pref[i] + (((unsigned __int128)1) << bit[i]);
}
vector<vector<int>> cost(p, vector<int>(p, INF));
for (int i = 0; i < p; i++) {
for (int j = i; j < p; j++) {
unsigned __int128 sum = pref[j + 1] - pref[i];
int hi = (j + 1 < p ? bit[j + 1] - 1 : LIM);
for (int h = bit[j]; h <= hi; h++) {
unsigned __int128 target = ((unsigned __int128)1) << h;
if (target < sum) continue;
cost[i][j] = min(cost[i][j], pop128(target - sum));
}
}
}
vector<vector<int>> dp(p + 1, vector<int>(K + 1, INF));
dp[0][0] = 0;
for (int i = 0; i < p; i++) {
for (int used = 0; used <= K; used++) {
if (dp[i][used] == INF) continue;
for (int j = i; j < p; j++) {
int c = cost[i][j];
if (c == INF || used + c > K) continue;
dp[j + 1][used + c] = min(dp[j + 1][used + c], dp[i][used] + 1);
}
}
}
int q = INF;
for (int used = 0; used <= K; used++) {
q = min(q, dp[p][used]);
}
cout << k + p - q << '\n';
}
}