1095C - Powers Of Two - CodeForces Solution

bitmasks greedy *1400

Please click on ads to support us..

Python Code: 

from sys import stdin, stdout

n, k = map(int, stdin.readline().split())

bits = list(map(lambda i: n >> i & 1, range(33)))

if k > n or k < sum(bits):
    print("NO")
else:
    ans = {i: bits[i] for i in range(33)}
    curr = sum(bits)

    for pow in range(32, 0, -1):
        if curr == k:
            break
        smt = min(ans[pow], k - curr)

        curr += smt
        ans[pow - 1] += 2 * smt
        ans[pow] -= smt

    print("YES")
    check = 0

    for i in range(33):
        pp = str(2**i)

        for app in range(ans[i]):
            check += int(pp)
            stdout.write(pp)
            stdout.write(" ")

    print()

C++ Code: 

#include <bits/stdc++.h>
using namespace std;
#define SR()                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define endl '\n'
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define all(s) s.begin(), s.end()

const double pi = acos(-1);
typedef long long ll;
typedef unsigned long long ull;
void File()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
}

int main()

{
    SR();
    ll n, m;
    cin >> n >> m;
    bitset<32> aa = n;
    // cout << aa << endl;
    priority_queue<ll> ppq;
    for (int i = 0; i < 32; i++)
    {
        if (aa[i] == 1)
        {
            ppq.push(pow(2, i));
        }
    }
    ll cnt = ppq.size();
    if (m < cnt || m > n)
        cout << "NO" << endl;
    else
    {
        cout << "YES" << endl;
        while (cnt++ != m)
        {
            ll ini = ppq.top();
            ppq.pop();
            ppq.push(ini / 2);
            ppq.push(ini / 2);
        }
        while(!ppq.empty())
        {
            cout << ppq.top() << " ";
            ppq.pop();
        }
        cout << endl;
    }

    return 0;
}


Comments

Submit
0 Comments
More Questions

Health of a person
Divisibility
A. Movement
Numbers in a matrix
Sequences
Split houses
Divisible
Three primes
Coprimes
Cost of balloons
One String No Trouble
Help Jarvis!
Lift queries
Goki and his breakup
Ali and Helping innocent people
Book of Potion making
Duration
Birthday Party
e-maze-in
Bricks Game
Char Sum
Two Strings
Anagrams
Prime Number
Lexical Sorting Reloaded
1514A - Perfectly Imperfect Array
580A- Kefa and First Steps
1472B- Fair Division
996A - Hit the Lottery
MSNSADM1 Football