AmebaDiv1.cpp

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

class AmebaDiv1
{
public:
	int count(vector <int> X);
};

int finalState(int st, vector <int> &mul) {
    for(auto it = (mul).begin(); it != (mul).end(); ++it) {
        if(st == *it)
            st *= 2;
    }
    return st;
}

int AmebaDiv1::count (vector <int> X)
{
    set <int> st;
    st.clear();
    for(auto it = (X).begin(); it != (X).end(); ++it) {
        st.insert(finalState(*it, X));
    }
    for(auto it = (st).begin(); it != (st).end(); ++it) {
        cout << *it << " ";
    }
    cout << "\n";

	int ret = 0;
    set <int> X1;
    X1.clear();
    for(auto it = (X).begin(); it != (X).end(); ++it) {
        X1.insert(*it);
    }
    for(auto it = (X1).begin(); it != (X1).end(); ++it) {
        if(st.find(*it) == st.end())
            ret++;
    }
	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, 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;
	AmebaDiv1 *obj;
	int answer;
	obj = new AmebaDiv1();
	clock_t startTime = clock();
	answer = obj->count(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;
	bool disabled;
	bool tests_disabled;
	all_right = true;
	tests_disabled = false;
	
	vector <int> p0;
	int p1;
	
	// ----- test 0 -----
	disabled = false;
	p0 = {3,2,1};
	p1 = 2;
	all_right = (disabled || KawigiEdit_RunTest(0, p0, true, p1) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 1 -----
	disabled = false;
	p0 = {2,2,2,2,2,2,4,2,2,2};
	p1 = 2;
	all_right = (disabled || KawigiEdit_RunTest(1, p0, true, p1) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 2 -----
	disabled = false;
	p0 = {1,2,4,8,16,32,64,128,256,1024,2048};
	p1 = 11;
	all_right = (disabled || KawigiEdit_RunTest(2, p0, true, p1) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 3 -----
	disabled = false;
	p0 = {854,250,934,1000,281,250,281,467,854,562,934,1000,854,500,562};
	p1 = 7;
	all_right = (disabled || KawigiEdit_RunTest(3, p0, true, p1) ) && 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
// Monte-Carlo is an amoeba. Amoebas can feed on gel: whenever an amoeba encounters a piece of gel that is exactly as big as the amoeba, the amoeba will consume the gel and thus double its size.
// 
// Initially, the size of Monte-Carlo was some unknown positive integer. During its lifetime, Monte-Carlo encountered several gels and consumed the ones it could.
// 
// You are given a vector <int> X. The elements of X are the sizes of gels Monte-Carlo encountered, in chronological order.
// 
// Let S be the set of all possible final sizes of Monte-Carlo. Compute and return the number of positive integers that do not belong into S.
// 
// DEFINITION
// Class:AmebaDiv1
// Method:count
// Parameters:vector <int>
// Returns:int
// Method signature:int count(vector <int> X)
// 
// 
// NOTES
// -It is possible to prove that the answer for any test case is finite and fits into a 32-bit signed integer type.
// 
// 
// CONSTRAINTS
// -X will contain between 1 and 200 integers, inclusive.
// -Each element of X will be between 1 and 1,000,000,000, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// {3,2,1}
// 
// Returns: 2
// 
// Here are a few possibilities how Monte-Carlo's life could have looked like:
// 
// Monte-Carlo started with size 1, ignored gel #0, ignored gel #1, consumed gel #2 and thus reached size 2.
// Monte-Carlo started with size 3, consumed gel #0 and thus reached size 6, and then ignored the next two gels (as they were too small).
// Monte-Carlo started with size 47 and ignored all three gels.
// 
// All final sizes except for 1 and 3 are possible.
// 
// 1)
// {2,2,2,2,2,2,4,2,2,2}
// 
// Returns: 2
// 
// If Monte-Carlo starts with size 2, its life will look as follows: First, it will consume gel #0 and thus grow to 4. Later, after ignoring a few gels, Monte-Carlo will consume gel #6 (the one with size 4) and thus grow to 8.
// 
// It can be shown that for this X Monte-Carlo's final size can never be 2 or 4. 
// 
// 2)
// {1,2,4,8,16,32,64,128,256,1024,2048}
// 
// Returns: 11
// 
// 
// 
// 3)
// {854,250,934,1000,281,250,281,467,854,562,934,1000,854,500,562}
// 
// Returns: 7
// 
// 
// 
// END KAWIGIEDIT TESTING