CollectingPayment.cpp

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cassert>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iterator>
#include <fstream>
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;
/*
#if __cplusplus > 199711L	// for g++0x, value of __cplusplus must be greater thana 199711L.
	#define tr(i, c)	for(auto i = begin(c); i != end(c); i++)
#else
	#define tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#endif
*/
#define endl		("\n")
#define tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define PI		M_PI
#define E 		M_E
#define	eps		1e-9

#define	Sf		scanf
#define	Pf		printf

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

#define	all(c)		(c).begin(), (c).end()
#define	CL(a, b)	memset(a, b, sizeof(a))
#define mp		make_pair
#define pb		push_back

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

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

#if (0 or defined ONLINE_JUDGE)
	#define DEBUG
#else 
	#define DEBUG(x)	cout << #x << " = " << x << "\n"
#endif

class CollectingPayment
{
public:
	double maximumProfit(vector <int> earning, vector <int> moment, int fee, int rate);
};

double CollectingPayment::maximumProfit (vector <int> earning, vector <int> moment, int fee, int rate) 
{
	double 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, vector <int> p1, int p2, int p3, bool hasAnswer, double p4) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p1.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p1[i];
	}
	cout << "}" << "," << p2 << "," << p3;
	cout << "]" << endl;
	CollectingPayment *obj;
	double answer;
	obj = new CollectingPayment();
	clock_t startTime = clock();
	answer = obj->maximumProfit(p0, p1, p2, p3);
	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" << p4 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == answer && fabs(p4 - answer) <= 1e-9 * max(1.0, fabs(p4));
	}
	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;
	vector <int> p1;
	int p2;
	int p3;
	double p4;
	
	{
	// ----- test 0 -----
	int t0[] = {300,290,320,150};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {120,124,200,202};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 40;
	p3 = 10;
	p4 = 1325.1174146859212;
	all_right = KawigiEdit_RunTest(0, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	int t0[] = {300,290,320,150};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {1,122,243,365};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 40;
	p3 = 10;
	p4 = 1240.733092976253;
	all_right = KawigiEdit_RunTest(1, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	int t0[] = {300,290,320,150};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {1,122,243,365};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 200;
	p3 = 10;
	p4 = 868.6;
	all_right = KawigiEdit_RunTest(2, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	int t0[] = {150};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {365};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 50;
	p3 = 100;
	p4 = 110.0;
	all_right = KawigiEdit_RunTest(3, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	int t0[] = {1000,1};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {155,365};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 100;
	p3 = 100;
	p4 = 17274.90824619758;
	all_right = KawigiEdit_RunTest(4, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	int t0[] = {1,346,7,346,345,3,453,5,346,3};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {1,2,7,34,74,163,200,250,352,360};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 0;
	p3 = 0;
	p4 = 1855.0;
	all_right = KawigiEdit_RunTest(5, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 6 -----
	int t0[] = {1,346,7,346,345,3,453,5,346,354,25,23,354,235,235};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {1,7,34,74,98,154,163,178,200,210,250,279,325,352,360};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 50;
	p3 = 10;
	p4 = 3693.6800093457805;
	all_right = KawigiEdit_RunTest(6, p0, p1, p2, p3, true, p4) && 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
// 
// You are working for a foreign company, doing your job remotely via the web.  Each time you deliver a task, a payment is added to your work account.  Anytime you want, you can ask the company to send you a check for your accumulated earnings, but a fixed fee is deducted from each check.  You will only ask for checks when your accumulated earnings are greater than or equal to fee.  When you ask for a check, the payments for tasks that are delivered on that same day will be included.  Checks arrive the same day that you request them, and they arrive before the bank closes, so you can deposit them into your bank account the same day.
// 
// The bank is open during the day every single day of the year.  Every Sunday night, after closing time, interest is added to your bank account in the amount of A*rate/1000, where A is the amount of money that was in your account at closing time.  Day 1 is a Sunday, so interest may be added to your bank account at the end of day 1, 8, 15, ..., 358, and 365.  At the beginning of day 1, your bank account has no money.
// 
// You are given two vector <int>s, earning and moment.  The ith element of earning specifies the payment you will receive for the ith task, and the ith element of moment is the day of the year (between 1 and 365) when you will deliver the ith task. You will also be given two ints fee and rate as described above. You must develop a strategy (deciding when to ask for your checks) that maximizes the amount of money you will have in your bank account after interest is added at the end of day 365.  Return this maximum amount.
// 
// 
// 
// DEFINITION
// Class:CollectingPayment
// Method:maximumProfit
// Parameters:vector <int>, vector <int>, int, int
// Returns:double
// Method signature:double maximumProfit(vector <int> earning, vector <int> moment, int fee, int rate)
// 
// 
// NOTES
// -At the end of the year, you may have some leftover earnings in your work account.  See example 4.
// -The returned value must be accurate to within a relative or absolute value of 1E-9.
// 
// 
// CONSTRAINTS
// -earning will contain between 1 and 50 elements, inclusive.
// -moment and earning will contain the same number of elements.
// -Each element of earning will be between 1 and 1000, inclusive.
// -Each element of moment will be between 1 and 365, inclusive.
// -The elements of moment will be sorted in strictly ascending order (no repeated elements).
// -fee will be between 0 and 1000, inclusive.
// -rate will be between 0 and 100, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// {300,290,320,150}
// {120,124,200,202}
// 40
// 10
// 
// Returns: 1325.1174146859212
// 
// One possible optimal strategy in this case is to ask for checks on days 125 and 203. In this case, your first check will be worth 550 (because it contains payments for your first two tasks less the fee: 300+290-40=550). On day 127 your bank account will be increased by 550*10/1000=5.5, getting to 555.5. After that, it will continue growing for another 10 Sundays, the last one being 197, getting to day 202 with 613.62 (approximately). On day 203 you deposit your check for 430 (320+150-40) and then your account is increased to 1043.62. On day 204 it will increase by 1043.62*10/1000, getting to 1054.05. From then on, it will increase another 23 times, the last one being on day 365.
// NOTE: All these partial results are rounded to only 2 digits, and therefore, lack precision. The final result reported, on the other hand, is precise.
// 
// 1)
// {300,290,320,150}
// {1,122,243,365}
// 40
// 10
// 
// Returns: 1240.733092976253
// 
// In this case, it is better to take a check for each payment to take advantage of the bank interest rate, because the times for payments are spread across the year.
// 
// 2)
// {300,290,320,150}
// {1,122,243,365}
// 200
// 10
// 
// Returns: 868.6
// 
// With such a big fee, it's preferable to wait until the end of the year and have all your payments sent together.
// 
// 3)
// {150}
// {365}
// 50
// 100
// 
// Returns: 110.0
// 
// You deposit right on time to get a 10% reward from the bank.
// 
// 4)
// {1000,1}
// {155,365}
// 100
// 100
// 
// Returns: 17274.90824619758
// 
// Here you should try to deposit the 1000 payment as fast as possible because of the high rate. Note that you will not request a check for the last payment because it is less than the fee.
// 
// 5)
// {1,346,7,346,345,3,453,5,346,3}
// {1,2,7,34,74,163,200,250,352,360}
// 0
// 0
// 
// Returns: 1855.0
// 
// With no fee and no interest rate, it doesn't matter when you ask for the checks.  As long as you collect every payment, your resulting balance will be equal to the sum of the payments.
// 
// 6)
// {1,346,7,346,345,3,453,5,346,354,25,23,354,235,235}
// {1,7,34,74,98,154,163,178,200,210,250,279,325,352,360}
// 50
// 10
// 
// Returns: 3693.6800093457805
// 
// 
// 
// END KAWIGIEDIT TESTING

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