UVA – 435 – Block Voting

Problem Statement: http://uva.onlinejudge.org/external/4/435.html

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define bit(n , i) ((n & (1 << i)) > 0)
int T, N, v[25], c[25];

int main() {

	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		scanf("%d", &N);
		for (int i = 0; i < N; ++i) scanf("%d", &v[i]);
		memset(c, 0, sizeof c);
		for (int s = 0; s < (1 << (N)); s++) {
			int sum[2] = {0,0};
			for (int i = 0; i < N; i++) sum[bit(s, i)] += v[i];

			for (int i = 0; i < N; i++) {
				if (bit(s, i)) {
					int sum_ = sum[bit(s, i)] - v[i],  half = ((sum[0] + sum[1]) / 2) + 1;
					if (sum_ <= half - 1 && sum_ + v[i] >= half)
						c[i]++;
				}
			}
		}
		for (int i = 0; i < N; i++)
			printf("party %d has power index %d\n", i + 1, c[i]);
		printf("\n");
	}
	return 0;
}
Advertisements

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

%d bloggers like this: