View Code of Problem 3846

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long a[1000];
int l;

long long C(long long a, long long b) {
    long long r1 = 1, r2 = 1;
    long long r = 1;
    for(int i = 0; i < a; i++) {
        r1 *= b;
        b--;
        r2 *= r;
        r++;
    }
    return r1 / r2;
}

long long pow2(long long x) {
    long long res = 1;
    for(long long i = 0; i < x; i++) {
        res *= 2;
    }
    return res;
}

void myadd(long long x) {
    long long x0;
    int i;/*
    for(i = 0; i < l; i++) {
            printf("%lld ", a[i]);
        }*/
        //printf("\n");
    while(x > 0) {
        //printf("%lld\n", x);
        x0 = a[0];
        i = 0;
        i++;
        while(a[i] == x0 + i) {
            i++;
        }
        a[i - 1]++;
        if(a[i - 1] - x0-1 == 0) {
            x -= a[i - 1] - x0;
        }
        else x -= C(a[i - 1] - x0 - 1, a[i - 1]);

        //printf("c(%lld %lld)\n", a[i - 1] - x0-1, a[i - 1]);

        i-=2;
        while(i >= 0 && a[i + 1] != 0) {
            a[i] = a[i + 1] - 1;
            i--;
        }
        /*
        for(i = 0; i < l; i++) {
            printf("%lld ", a[i]);
        }
        */
        //printf("\n");
    }
}

int main() {
    int t;
    long long n, k;
    scanf("%d", &t);
    int j;
    for(int ti = 1; ti <= t; ti++) {
        scanf("%lld%lld", &n, &k);
        l = 0;
        int r;
        j = 0;

        while(n > 0) {
            r = n % 2;
            if(r == 1) {
                a[l++] = j;
            }
            j++;
            n /= 2;
        }
        long long sum = C(l - 1, j - 1) - 1;
        //printf("sum = %lld\n", sum);
        if(sum < k) {
            printf("Case #%d: IMPOSSIBLE\n", ti);
            continue;
        }
        myadd(k);
        printf("Case #%d: ", ti);
        long long ans = 0;
        for(int i = 0; i < l; i++) {
            ans += pow2(a[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}