UVA 11933 - Splitting Numbers

Nithin SJ — Wed, 17 Mar 2021 11:48:54 +0000

Problem statement
We define the operation of splitting a binary number n into two numbers a(n), b(n) as follows. Let 0 ≤ i1 < i2 < . . . < ik be the indices of the bits (with the least significant bit having index 0) in n that are 1. Then the indices of the bits of a(n) that are 1 are i1, i3, i5, . . . and the indices of the bits of b(n) that are 1 are i2, i4, i6, . . . For example, if n is 110110101 in binary then, again in binary, we have a = 010010001 and b = 100100100.
Input
Each test case consists of a single integer n between 1 and 231 − 1 written in standard decimal (base 10) format on a single line. Input is terminated by a line containing ‘0’ which should not be processed.
Output
The output for each test case consists of a single line, containing the integers a(n) and b(n) separated by a single space. Both a(n) and b(n) should be written in decimal format.
Sample Input
6
7
13
0
Sample Output
2 4
5 2
9 4

Observation
Here, for every time ith bit is set, set ith bit of a and b alternatively.

Code

/*
Author : humanbeeng
*/
#include <bits/stdc++.h>
using namespace std;
#define fo(i, n) for (int i = 0; i < n; i++)
#define pb(num) push_back(num)
#define ppb pop_back()
#define all(arr) arr.begin(), arr.end()
#define pi(arr)                                            \
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) \
    cout << arr[i] << ' '
#define imn INT_MIN
#define imx INT_MAX
#define mod 1000000007
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ii> vii;
typedef vector<char> vc;
typedef unsigned long long ull;
typedef set<string, int> ssi;
typedef set<int> si;
typedef set<string> ss;

void setio(string s) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main() {
    //setio("");
    int num;
    while (cin >> num && num != 0) {
        bitset<32> a(0);
        bitset<32> b(0);
        bitset<32> n(num);
        int sw = 0;
        int i = 0;
        while(i<32){
            if(n.test(i) && sw == 0){
                a.set(i);
                sw = 1;
            }else if(n.test(i) && sw == 1){
                b.set(i);
                sw = 0;
            }
            i++;
        }
        int aa = a.to_ulong();
        int bb = b.to_ulong();
        cout << aa << " " << bb << endl;


    }

    return 0;
}

DEV Community: Nithin SJ

UVA 11933 - Splitting Numbers