DrawingMarbles.cpp

#include <bits/stdc++.h>
using namespace std;

class DrawingMarbles
{
public:
	double sameColor(vector <int> colors, int n);
};

double P(int k, int n, int total) {
    if(k>n)
        return 0;
    else if(k == 0)
        return 1.0;
    else
        return P(k-1, n, total)*(n-(k-1.0))/(total-(k-1.0));
}

double DrawingMarbles::sameColor (vector <int> colors, int n)
{
	double ret = 0;
    int total = accumulate(colors.begin(), colors.end(), 0);

    for(int i = 0; i < (int)colors.size(); ++i) {
        ret += P(n, colors[i], total);
    }
	return ret;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit-pf 2.3.0
#include <iostream>
#include <string>
#include <vector>
#include <ctime>
#include <cmath>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, int p1, bool hasAnswer, double p2) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << p1;
	cout << "]" << endl;
	DrawingMarbles *obj;
	double answer;
	obj = new DrawingMarbles();
	clock_t startTime = clock();
	answer = obj->sameColor(p0, p1);
	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" << p2 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == answer && fabs(p2 - answer) <= 1e-9 * max(1.0, fabs(p2));
	}
	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;
	bool disabled;
	bool tests_disabled;
	all_right = true;
	tests_disabled = false;
	
	vector <int> p0;
	int p1;
	double p2;
	
	// ----- test 0 -----
	disabled = false;
	p0 = {13};
	p1 = 8;
	p2 = 1.0;
	all_right = (disabled || KawigiEdit_RunTest(0, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 1 -----
	disabled = false;
	p0 = {5,7};
	p1 = 1;
	p2 = 1.0;
	all_right = (disabled || KawigiEdit_RunTest(1, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 2 -----
	disabled = false;
	p0 = {5,6,7};
	p1 = 2;
	p2 = 0.3006535947712418;
	all_right = (disabled || KawigiEdit_RunTest(2, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 3 -----
	disabled = false;
	p0 = {12,2,34,13,17};
	p1 = 4;
	p2 = 0.035028830818304504;
	all_right = (disabled || KawigiEdit_RunTest(3, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	if (all_right) {
		if (tests_disabled) {
			cout << "You're a stud (but some test cases were disabled)!" << endl;
		} else {
			cout << "You're a stud (at least on given cases)!" << endl;
		}
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// A big box contains marbles of one or more colors. You're given a vector <int> colors, each element of which denotes the number of marbles there are of a particular color. You draw n marbles randomly from the box, leaving each marble outside the box after taking it. Return the probability that all marbles drawn will be the same color.
// 
// DEFINITION
// Class:DrawingMarbles
// Method:sameColor
// Parameters:vector <int>, int
// Returns:double
// Method signature:double sameColor(vector <int> colors, int n)
// 
// 
// NOTES
// -Every time we draw a marble, all marbles in the box are equally likely to be chosen.
// -A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
// 
// 
// CONSTRAINTS
// -colors will contain between 1 and 50 elements, inclusive.
// -Each element of colors will be between 1 and 50, inclusive.
// -n will be between 1 and the sum of all elements of colors, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// { 13 }
// 8
// 
// Returns: 1.0
// 
// All the marbles are the same color, so obviously all drawn marbles will be the same color too.
// 
// 1)
// { 5, 7 }
// 1
// 
// Returns: 1.0
// 
// 
// 
// 2)
// { 5, 6, 7 }
// 2
// 
// Returns: 0.3006535947712418
// 
// The probability that the first drawn marble will be of the color 0 is 5 / 18 (there are 5 marbles of color 0 out of 18). If the first drawn marble is of the color 0, then the probability that the second drawn marble will be of the color 0 is 4 / 17 (there are 4 marbles of color 0 left out of 17). So the probability that both drawn marbles will be of the color 0 is (5 / 18) * (4 / 17) = 0.0653594771... . Similarly, the probability that both drawn marbles will be of the color 1 is (6 / 18) * (5 / 17) = 0.0980392156..., and that both drawn marbles will be of the color 2 is (7 / 18) * (6 / 17) = 0.1372549019... . The answer is the sum of these 3 probabilities.
// 
// 3)
// { 12, 2, 34, 13, 17 }
// 4
// 
// Returns: 0.035028830818304504
// 
// 
// 
// END KAWIGIEDIT TESTING