UVa : 11532 (Simple Adjacency Maximization)


One of the problems from my first contest ULAB NCPC 2008. This is the 2nd most solvable problem.
1. Smallest integer, where P 1’s and Q 0’s
suppose P = 5, Q = 7
ans : 000000011111
but there is another condition
2. “number of 1s adjacent to one or more 0 in the binary representation is maximized”
suppose P = 6 and Q = 7
output : 0000 101 101 101
3. If the number of zeros aren’t enough to make this pattern then choose the best position for zeros
if P = 4 and Q = 1
output : 10111 = 23
4. If P = 1 and Q = 1
output : 01 = 1


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

LL powerOf2 (int b)
{
	LL ret = 1;

	for ( int i = 1; i <= b; i++ ) ret *= 2;

	return ret;
}

void makeDecimal (string s)
{
    LL ret = 0;

    for ( size_t i = 0; i < s.length (); i++ ) {
        ret += (powerOf2 (i) * (s.at (i) - '0'));
    }

    cout << ret << endl;
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);

    while ( testCase-- ) {
        int p, q; scanf ("%d %d", &p, &q);

        string str = "";

        while ( p >= 2 && q >= 1 ) {
            str += "101";
            p -= 2;
            q--;
        }

        if ( p == 1 && q >= 1 ) { str = "01" + str; p--; q--; }
        for ( int i = 0; i < p; i++ ) str += "1";

        reverse (str.begin (), str.end ());

        makeDecimal (str);
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s