docker_space/frontier_cs_8/analyze.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    // For S = 2^30 - 2 (worst case: k = 2^31 - 3)
    long long S = (1LL << 30) - 2;
    
    int best_cost = 999;
    int best_m = -1;
    
    for (int m = 1; m <= 500; m++) {
        long long T = S + m;
        if (T & 1) continue; // T must be even
        if (T < 2LL * m) continue;
        
        // Get bits of T at positions >= 1
        vector<int> bits;
        int sum_bits = 0;
        for (int b = 1; b <= 40; b++) {
            if ((T >> b) & 1) {
                bits.push_back(b);
                sum_bits += b;
            }
        }
        
        int pc = bits.size();
        if (pc > m) continue;
        
        // Need m - pc splits
        int splits = m - pc;
        
        // Simulate splitting (smallest >= 2 first)
        multiset<int> exps(bits.begin(), bits.end());
        int cost = sum_bits;
        bool valid = true;
        
        for (int s = 0; s < splits; s++) {
            auto it = exps.lower_bound(2);
            if (it == exps.end()) { valid = false; break; }
            int d = *it;
            exps.erase(it);
            exps.insert(d - 1);
            exps.insert(d - 1);
            cost += (d - 2);
        }
        
        if (!valid) continue;
        
        int total = cost + 1;
        if (total < best_cost) {
            best_cost = total;
            best_m = m;
        }
    }
    
    cout << "Best cost: " << best_cost << " with m = " << best_m << endl;
    
    // Also check what happens for k = 2^31 - 1
    S = (1LL << 30) - 1;
    best_cost = 999;
    for (int m = 1; m <= 500; m++) {
        long long T = S + m;
        if (T & 1) continue;
        if (T < 2LL * m) continue;
        
        vector<int> bits;
        int sum_bits = 0;
        for (int b = 1; b <= 40; b++) {
            if ((T >> b) & 1) {
                bits.push_back(b);
                sum_bits += b;
            }
        }
        
        int pc = bits.size();
        if (pc > m) continue;
        
        int splits = m - pc;
        multiset<int> exps(bits.begin(), bits.end());
        int cost = sum_bits;
        bool valid = true;
        
        for (int s = 0; s < splits; s++) {
            auto it = exps.lower_bound(2);
            if (it == exps.end()) { valid = false; break; }
            int d = *it;
            exps.erase(it);
            exps.insert(d - 1);
            exps.insert(d - 1);
            cost += (d - 2);
        }
        
        if (!valid) continue;
        
        int total = cost + 1;
        if (total < best_cost) {
            best_cost = total;
            best_m = m;
        }
    }
    
    cout << "For 2^31-1: Best cost: " << best_cost << " with m = " << best_m << endl;
    
    // Find the WORST case S in [0, 2^30-1]
    // Test a range of difficult S values
    int worst_cost = 0;
    long long worst_S = 0;
    
    for (long long s = (1LL << 30) - 100; s <= (1LL << 30) - 1; s++) {
        int bc = 999;
        for (int m = 1; m <= 100; m++) {
            long long T = s + m;
            if (T & 1) continue;
            if (T < 2LL * m) continue;
            
            vector<int> bits;
            int sb = 0;
            for (int b = 1; b <= 40; b++) {
                if ((T >> b) & 1) { bits.push_back(b); sb += b; }
            }
            
            int pc = bits.size();
            if (pc > m) continue;
            
            int sp = m - pc;
            multiset<int> exps(bits.begin(), bits.end());
            int cost = sb;
            bool valid = true;
            for (int ss = 0; ss < sp; ss++) {
                auto it = exps.lower_bound(2);
                if (it == exps.end()) { valid = false; break; }
                int d = *it;
                exps.erase(it);
                exps.insert(d-1);
                exps.insert(d-1);
                cost += (d-2);
            }
            if (!valid) continue;
            int total = cost + 1;
            if (total < bc) bc = total;
        }
        if (bc > worst_cost) {
            worst_cost = bc;
            worst_S = s;
        }
    }
    
    cout << "Worst case near 2^30: S = " << worst_S << " cost = " << worst_cost << endl;
    
    return 0;
}