ConnectTheCities.cpp

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

class ConnectTheCities
{
public:
	int minimalRange(int distance, int funds, vector <int> position);
};

int cost(int range, int lastPos){
    if(lastPos - range <= 0)
        return 0;
    else
        return lastPos - range + cost(range, lastPos-range);
}

int ConnectTheCities::minimalRange (int distance, int funds, vector <int> position)
{
	int ret = (int)1e9;
    for(int range = (int)1; range <= (int)distance; ++range) {
        if(cost(range, distance) <= funds)
            ret = min(ret, range);
    }
	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, int p0, int p1, vector <int> p2, bool hasAnswer, int p3) {
	cout << "Test " << testNum << ": [" << p0 << "," << p1 << "," << "{";
	for (int i = 0; int(p2.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p2[i];
	}
	cout << "}";
	cout << "]" << endl;
	ConnectTheCities *obj;
	int answer;
	obj = new ConnectTheCities();
	clock_t startTime = clock();
	answer = obj->minimalRange(p0, p1, p2);
	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" << p3 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p3;
	}
	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;
	
	int p0;
	int p1;
	vector <int> p2;
	int p3;
	
	// ----- test 0 -----
	disabled = false;
	p0 = 10;
	p1 = 5;
	p2 = {3,7,9};
	p3 = 3;
	all_right = (disabled || KawigiEdit_RunTest(0, p0, p1, p2, true, p3) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 1 -----
	disabled = false;
	p0 = 20;
	p1 = 100;
	p2 = {0,0,0,0};
	p3 = 4;
	all_right = (disabled || KawigiEdit_RunTest(1, p0, p1, p2, true, p3) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 2 -----
	disabled = false;
	p0 = 63;
	p1 = 19;
	p2 = {34,48,19,61,24};
	p3 = 12;
	all_right = (disabled || KawigiEdit_RunTest(2, p0, p1, p2, true, p3) ) && 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 and B are two cities distance units away from each other. Several transmitters have been placed along the straight road connecting them. 
// The transmission range can be set to any positive integer value, but it must be the same for all transmitters.
// Any two transmitters can communicate directly if the distance between them is not greater than the transmission range.
//   Each transmitter can communicate with city A or city B if the distance between the transmitter and the city is not greater than the transmission range. 
// 
// You have been assigned to set up a connection between the cities. You are allowed to move any number of transmitters, but moving a transmitter for k units costs you k dollars and the budget does not allow you to spend more than funds dollars in total. You can move the transmitters into points with integer coordinates only.
// 
// You will be given a vector <int> position, with the i-th element of position representing the initial distance between the i-th transmitter and city A. You will be also given funds, the maximal total cost you are allowed to spend when moving transmitters.
// Return the minimal transmission range which still allows you to establish a connection between the cities. See notes for the formal definition of the connection.
// 
// 
// 
// DEFINITION
// Class:ConnectTheCities
// Method:minimalRange
// Parameters:int, int, vector <int>
// Returns:int
// Method signature:int minimalRange(int distance, int funds, vector <int> position)
// 
// 
// NOTES
// -Cities A and B are connected if there exists a sequence of transmitters t1, t2, ..., tn such that transmitter t1 can communicate directly with city A, transmitter tn can communicate directly with city B and, for every i between 1 and n-1, inclusive, transmitters ti and ti+1 can communicate directly.
// 
// 
// CONSTRAINTS
// -distance will be between 1 and 100, inclusive.
// -position will contain between 1 and 50 elements, inclusive.
// -Each element of position will be between 0 and distance, inclusive.
// -funds will be between 0 and 100000, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// 10
// 5
// { 3, 7, 9 }
// 
// Returns: 3
// 
// We can move the second transmitter one unit left and the range of 3 units will be enough for a connection.
// 
// 1)
// 20
// 100
// { 0, 0, 0, 0 }
// 
// Returns: 4
// 
// We have enough money to place transmitters at positions 4, 8, 12 and 16.
// 
// 2)
// 63
// 19
// { 34, 48, 19, 61, 24 }
// 
// Returns: 12
// 
// 
// 
// END KAWIGIEDIT TESTING