DengklekTryingToSleep.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--)

class DengklekTryingToSleep
{
public:
	int minDucks(vector <int> ducks)
	{
		int ret = 0;
		int mn = *min_element(all(ducks));
		int mx = *max_element(all(ducks));
		
		forab(i, mn, mx)
			if(!cpresent(i, ducks))
				ret++;
		
		return ret;
	}
};

// 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;
	DengklekTryingToSleep *obj;
	int answer;
	obj = new DengklekTryingToSleep();
	clock_t startTime = clock();
	answer = obj->minDucks(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[] = {5,3,2};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 1;
	all_right = KawigiEdit_RunTest(0, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	int t0[] = {58};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 0;
	all_right = KawigiEdit_RunTest(1, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	int t0[] = {9,3,6,4};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 3;
	all_right = KawigiEdit_RunTest(2, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	int t0[] = {7,4,77,47,74,44};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 68;
	all_right = KawigiEdit_RunTest(3, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	int t0[] = {1,2,3,4,5,6,7,8,9,10};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 0;
	all_right = KawigiEdit_RunTest(4, 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
// Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks live together in peace and harmony. The ducks are numbered by distinct positive integers from A to B, inclusive, where A <= B.
// 
// Last night, Mr. Dengklek could not sleep, so he tried to count all the ducks in the kingdom. (It is known that counting ducks can help people to fall asleep.) When counting the ducks, Mr. Dengklek walked across an imaginary meadow and whenever he saw a new duck, he called out its number. He only called out actual duck numbers, i.e., numbers from A to B. He never called the same number twice. The numbers he called out are not necessarily in the numeric order.
// 
// You are given a vector <int> ducks. The elements of ducks are the numbers Mr. Dengklek called out when counting the ducks last night. It is possible that he missed some of the ducks. Obviously, the number of ducks he missed depends on the values A and B. The values of A and B are unknown to you. Compute and return the smallest possible number of ducks Mr. Dengklek might have missed.
// 
// DEFINITION
// Class:DengklekTryingToSleep
// Method:minDucks
// Parameters:vector <int>
// Returns:int
// Method signature:int minDucks(vector <int> ducks)
// 
// 
// CONSTRAINTS
// -ducks will contain between 1 and 50 elements, inclusive.
// -Each element of ducks will be between 1 and 100, inclusive.
// -All element of ducks will be distinct.
// 
// 
// EXAMPLES
// 
// 0)
// {5, 3, 2}
// 
// Returns: 1
// 
// If A=2 and B=5, the only duck Mr. Dengklek missed is the duck number 4.
// 
// 1)
// {58}
// 
// Returns: 0
// 
// If A=B=58, Mr. Dengklek did not miss any ducks.
// 
// 2)
// {9, 3, 6, 4}
// 
// Returns: 3
// 
// In this case, the smallest possible number of missed ducks is 3: the ducks with numbers 5, 7, and 8.
// 
// 3)
// {7, 4, 77, 47, 74, 44}
// 
// Returns: 68
// 
// 
// 
// 4)
// {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
// 
// Returns: 0
// 
// 
// 
// END KAWIGIEDIT TESTING




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