ElectionFraudDiv1.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
using namespace std;

typedef long long  int64;
typedef vector<int> vi;
typedef string ST;
typedef stringstream SS;
typedef vector< vector <int> > vvi;
typedef pair<int,int> ii;
typedef vector <string> vs;

#define Pf	printf
#define	Sf	scanf

#define	ep	1e-9
#define PI M_PI
#define E M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp	make_pair

#define	pb	push_back

#define	all(c)	(c).begin(), (c).end()
#define	tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

#define	present(x, c)	((c).find(x) != (c).end())		//map & set//
#define	cpresent(x, c)	(find(all(c),x) != (c).end())	//vector & list//

#define forn(i, n)	for(int i = 0, loop_ends_here = (int)n; i < loop_ends_here; i++)
#define forab(i, a, b)	for(int i = a, loop_ends_here = (int) b; i <= loop_ends_here; i++)
#define rep(i, a, b)	for(int i = a, loop_ends_here = (int)b; i>=loop_ends_here; i--)

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)

class ElectionFraudDiv1
{
public:
	int MinimumVoters(vector <int> percentages);
};

vector<int64> p;

bool check(int64 d) {
	bool ret = true;

//	cout << "D =" << d << endl;
	forn(i, p.size()) {
		int64 xi = round(p[i]*d/100.0);
		int64 pi = round(xi * 100.0 / d);

//		Pf("d = %lld, p[i] = %lld, xi = %lld, pi = %lld\n", d, p[i], xi, pi);
		ret &= (pi == p[i] ? true : false);
	}
//	cout << endl;
	return ret;
}

int ElectionFraudDiv1::MinimumVoters (vector <int> percentages) 
{
	p.clear();
	forn(i, percentages.size())	p.pb(percentages[i]);
	
	if(accumulate(all(p), 0ll) < 100)	return -1;

	int64 low = 1ll, high = 1e11;
/*
	rep(i, 100, 1)
		if(!check(i))
			return i;
*/
	forab(i, low, 1e5) {
		if(check(i));
			return i;
	}
	
	return -1;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, bool hasAnswer, int p1) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}";
	cout << "]" << endl;
	ElectionFraudDiv1 *obj;
	int answer;
	obj = new ElectionFraudDiv1();
	clock_t startTime = clock();
	answer = obj->MinimumVoters(p0);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p1 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p1;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <int> p0;
	int p1;
	
	{
	// ----- test 0 -----
	int t0[] = {9,27,64};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 11;
	all_right = KawigiEdit_RunTest(0, p0, true, p1) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// In a normal election, one expects the percentages received by each of the candidates to sum to exactly 100 percent.  There are two ways this might not be the case: if the election is fraudulent, or if the reported percentages are rounded.
// For example, in an election with 3 voters and 3 candidates, if each voter chooses a different candidate the final percentages would be reported as 33, 33, 33, which only sum to 99.  Conversely, in an election with 7 voters and 3 candidates, if the candidates receive 2, 2, and 3 votes, respectively, the final percentages would be reported as 29, 29, and 43, which sum to 101.
// The ministry of voting wants you to help them determine if an election was run fairly or not.  You'll be given a vector <int> percentages, giving the percentage of the vote that went to each candidate, rounded to the nearest whole number (in the case a number lies halfway between 2 consecutive integers, it will be rounded up).  If the election could be legitimate, return the minimum number of voters that could have participated in this election.  If the election is definitely fraudulent, return -1.
// 
// DEFINITION
// Class:ElectionFraudDiv1
// Method:MinimumVoters
// Parameters:vector <int>
// Returns:int
// Method signature:int MinimumVoters(vector <int> percentages)
// 
// 
// NOTES
// -You may assume that whenever the election may be legitimate, the smallest possible number of voters will fit into a int.
// 
// 
// CONSTRAINTS
// -percentages will contain between 1 and 50 elements, inclusive.
// -Each element of percentages will be between 0 and 100, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// {33, 33, 33}
// 
// Returns: 3
// 
// The first example from the problem statement.
// 
// 1)
// {29, 29, 43}
// 
// Returns: 7
// 
// The second example from the problem statement.
// 
// 2)
// {12, 12, 12, 12, 12, 12, 12, 12}
// 
// Returns: -1
// 
// These results are impossible.
// 
// 3)
// {13, 13, 13, 13, 13, 13, 13, 13}
// 
// Returns: 8
// 
// 
// 
// 4)
// {0, 1, 100}
// 
// Returns: 200
// 
// The only possibility is that the candidates received 0, 1, and 199 votes, respectively.
// 
// 5)
// {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4}
// 
// Returns: 97
// 
// 
// 
// END KAWIGIEDIT TESTING


//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!