Add files using upload-large-folder tool

1fd0050 verified 6 months ago

4.23 kB

#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;
}

	#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;
	}