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.
The binary representation is huge, so forget converting it to an integer. The only thing that matters for each operation is the last bit: means even, means odd.
Dividing by in binary is just deleting the last bit. Adding is annoying only because it creates a carry. So ask yourself: can we process bits from right to left while remembering only whether there is a carry?
When you are looking at some bit with carry , the effective value is . If it is even, one operation deletes this bit. If it is odd, you must add first, then delete it.
For every bit except the most significant one:
Scan from the last bit down to index . Maintain .
If or , answer increases by . If , answer increases by and . After the scan, if , add one final division because the leading became binary .
The number has up to binary digits. So if your plan starts with “convert it to integer”, congratulations, you have invented overflow.
We need to work directly with the string.
The operations are simple in binary:
So the whole problem is basically: process bits from right to left, while tracking whether previous additions created a carry.
Ignore the most significant bit for now. Suppose we are processing bit , and there is a carry , where .
The effective value of this bit is:
There are three cases.
The number is even at this bit. We just divide by , deleting the bit.
Cost: operation.
Carry remains .
The number is odd. We must first add , then divide by .
Cost: operations.
Adding creates a carry into the next bit, so .
This means original bit was and carry was already :
The current bit becomes , and the carry continues. Since the current bit is effectively even, we only divide by .
Cost: operation.
Carry remains .
We scan only indices , because once all lower bits are removed, only the leading part remains.
The first digit is always .
Therefore, after the loop, add to the answer.
For :
Scanning from right to left excluding the first bit:
The costs become:
The last is the final carry division.
We process each bit once and store only a couple of integers.
Fast, clean, and no big integer nonsense.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
string s;
cin >> s;
ll ans = 0;
int carry = 0;
for (int i = (int)s.size() - 1; i >= 1; --i) {
int cur = (s[i] - '0') + carry;
if (cur == 0) {
// Even: just divide by 2, removing this bit.
ans += 1;
} else if (cur == 1) {
// Odd: add 1, then divide by 2. This creates a carry.
ans += 2;
carry = 1;
} else {
// cur == 2: effective bit is 0, carry continues.
ans += 1;
}
}
// If the leading 1 received a carry, it became binary 10,
// so one more division is needed.
ans += carry;
cout << ans << '\n';
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
string s;
cin >> s;
ll ans = 0;
int carry = 0;
for (int i = (int)s.size() - 1; i >= 1; --i) {
int cur = (s[i] - '0') + carry;
if (cur == 0) {
// Even: just divide by 2, removing this bit.
ans += 1;
} else if (cur == 1) {
// Odd: add 1, then divide by 2. This creates a carry.
ans += 2;
carry = 1;
} else {
// cur == 2: effective bit is 0, carry continues.
ans += 1;
}
}
// If the leading 1 received a carry, it became binary 10,
// so one more division is needed.
ans += carry;
cout << ans << '\n';
}