CodeInvicta: CINVIT04: EDITORIAL
Problem:
Freelance Client
Problem:
The Chef got a freelance project, he has to make a machine learning (ML) model for his client and there are only HH hours left for submission of his model. He uses Emmazon web services (EWS) to make the ML model. The Chef needs to process the data sent by the client to make the ML model. The size of the data, Chef needs to process is GG(in Gigabytes).
Chef has a plan in his EWS account which allows him to process one Gigabyte per KK hours.
In addition to this Chef can pay and take some temporary plans to speed up his processes, those plans are:
-
Plan 1: Process G1G1 gigabytes at the cost of 1GB1GB per H1H1 hours at the cost of B1B1 Booge Coins.
-
Plan 2: Process G2G2 gigabytes at the cost of 1GB1GB per H2H2 hours at the cost of B2B2 Booge Coins.
The Chef’s account is postpaid so there’s no time wasted while switching plans, the costs will be added directly to his bill. The chef can buy and use a plan multiple times, but he can only use one plan at a time. once a Temporary plan is bought it replaces the regular plan until the data limit of the temporary plan is completely exhausted. After the temporary plan is consumed, he can buy another temporary plan or switch to his free normal plan present in his account.
Find the minimum number of Booge Coins Chef has to pay to EWS to process GG gigabytes data in no more than HH hours.
Note: EWS can only process an integer number of gigabytes using any plan. EWS can’t process a gigabyte partially using multiple plans (i.e., No fractions).
Input
The first line contains the size of data (GG), model submission deadline (HH) and number of Hours taken to process 1GB 1GB of data using his default EWS plan (KK). This line should contain Integers G, HandKG, HandK.
The second line has the details of the first temporary plan. this line should have three Integer numbers G1,H1 G1,H1 and B1B1.
The third line has the details of the second temporary plan. this line should have three Integer numbers G2,H2 G2,H2 and B2B2.
Output
Output the minimum amount of BOOGE coins Chef has to pay to EWS to process GG gigabytes data in no more than HH hours.
If there exists no solution for given conditions, output −1−1.
Constraints
- First Line in Input: 1 ≤ G, H, K ≤ 1071 ≤ G, H, K ≤ 107
- Second Line: 1 ≤ G1, H1, B1 ≤ 1071 ≤ G1, H1, B1 ≤ 107
- Third Line: 1 ≤ G2, H2, B2 ≤ 107
Approach:
We Will Iterate through every Gb of data and choose the best plan for every Iteration. Read comments
and see the if-else conditions in the code it is self-explanatory.
Sample Input
120 964 20
26 8 8
13 10 4
Sample Output
40
Solution
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
ll G,H,K,G1,H1,B1,G2,H2,B2;
cin>>G>>H>>K>>G1>>H1>>B1>>G2>>H2>>B2;
ll maxPossibleTime = 100000000;//Max Possible time given in constraints = 10^7
ll ans = maxPossibleTime;
for (long i = 0; i <= G; i++) { //Iterating over every GigaByte of Data
ll cost = ((i + G1 - 1) / G1) * B1; //cost using 1st temporary plan
ll remainingTime = H - i * H1;//Time remaing before deadline
ll remainingGB = G - i;//remaing Gb to process
if (remainingTime < 0) break; //If no time is left exit loop
else if (remainingTime >= K * remainingGB) ans = min(ans, cost);
if (H2 < K) {
if ((K * remainingGB - remainingTime) < 0) break;
ll x = ((K * remainingGB - remainingTime) + K - H2 - 1) / (K - H2);
if (x <= remainingGB) ans = min(ans, cost + ((x + G2 - 1) / G2) * B2);
}
}
cout<<(ans==maxPossibleTime? -1:ans)<<endl;
return 0;
}
Explanation:
For a minimal cost, Chef has to take the 1st temporary plan 5 times and do not buy the 2nd plan. He processes 120 GB (26x5=130GB is available to use) Time taken is 960 hours (120x8=960).
The client wanted it before 964 hours. Chef paid EWS 8·5 = 4040 Booge Coins for it.