Problem Link:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Akshat mangal
Tester: Radostin Chonev
Editorialist: Ritesh Gupta
DIFFICULTY:
EASY
PREREQUISITES:
Math, Observation
PROBLEM:
Initially, you are at 1 with empty tank and need to travel at N with your car. To travel 1 Km, you need 1 liter of water. There is a gas station after each 1 Km means at 1, 2, …, N, but the cost of filling 1 liter of gas at a gas station is equal to the number of gas station. you can not store more than V liters of gas in the tank of a car. Find both minimum as well as the maximum cost of filling that can happen to reach at N.
QUICK EXPLANATION:
As cost of the gas is increasing by going towards the N and we need only 1 liter of gas to reach from i-th station to (1+1)-th station
- which means that to maximise the cost, we can only take 1 liter of gas at each station. So, we need to travel total N-1 Km and we are starting from 1 that means (N*(N-1))/2 is the maximum cost.
- which means that to minimise the cost, we can try to fill the tank as soon as there is some empty space. So, we are filling the tank with V liters at station 1 and after that at each station we are consuming 1 liter to reach there so filling that 1 liter at that station itself. This way minimum cost is ((N - V)*(N - V + 1))/2 + V - 1 but if the tank capacity V is more or equal to N-1 then the minimum cost is (N-1) only.
EXPLANATION:
Maximum Cost:
As cost of filling the gas at each station is more then it’s previous one, to maximise the cost we try to buy gas from a station which is giving us in more money. Or if we have a choice that we can buy the gas either from i-th station or (i+x)-th station where x > 0 then we better choice would be to choose (i+x) station.
So, at any station will buy only the gas which will help us to reach the next station.
- at station 1, we take 1 liter gas which cost us 1 and we can go upto station 2
- at station 2, we take 1 liter gas which cost us 1 and we can go upto station 3
… - at station N-1, we take 1 liter gas which cost us N-1 and we can go upto station N
Overall cost is (1 + 2 + ... + (N-1)) or (N*(N-1))/2
Minimum Cost:
As cost of filling the gas at each station is more then it’s previous one, to minimise the cost, we need to do the opposite of the maximum or if we have a choice that we can buy the gas either from i-th station or (i+x)-th station where x > 0 then we better choice would be to choose (i) station.
Now, if we have enough capacity in the tank then we can fill the tank at station 1 only with the required gas and complete the journey. Mathematically, if V >= (N-1) then minimum cost will be (N-1)
Otherwise, we try to fill the tank as soon as possible.
- at station 1, we take V liter gas which cost us V and we reach station 2
- at station 2, we take 1 liter gas which cost us 2 and we reach station 3
… - at station N-V, we take 1 liter gas which cost us N-V and we reach station N-V+1
- at station N-V+1, we take 0 liter gas which cost us 0 and we reach station N-V+2
… - at station N-2, we take 0 liter gas which cost us 0 and we reach station N-1
- at station N-1, we take 0 liter gas which cost us 0 and we reach station N
Overall cost is (V + 2 + 3 + ... + (N-V)) or ((N - V)*(N - V + 1))/2 + V - 1
TIME COMPLEXITY:
O(1) per testcase
CODE:
Setter (C++)
#include
typedef long long ll;
using namespace std;
void pre()
{
}
void solve()
{
ll n,v;
cin>>n>>v;
ll min_cost;
if(n-1<=v)
min_cost=n-1;
else
min_cost=v+(n-v)*(n-v+1)/2-1;
cout<<n*(n-1)/2<<" "<<min_cost<<'\n';
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout<<fixed<>t;
for(ll tt=1;tt<=t;tt++)
{
// cout<<"Test Case #"<<tt<<": \n";
solve();
}
return 0;
}
Tester (C++)
#include
using namespace std ;
int n , v ;
void input ( ) {
cin >> n >> v ;
}
void solve ( ) {
if ( v >= n - 1 ) {
cout << 1LL * n * ( n - 1 ) / 2 << " " << n - 1 << "\n" ;
}
else {
cout << 1LL * n * ( n - 1 ) / 2 << " " << v + ( 1LL * ( n - v + 1 ) * ( n - v ) / 2 - 1 ) <> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}
Editorialist (C++)
#include
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
long long n,v;
cin >> n >> v;
if (v >= n-1) {
cout << (n*(n-1))/2 << " " << n-1 << endl;
} else {
cout << (n*(n-1))/2 << " " << ((n-v)*(n-v+1))/2 + v - 1 << endl;
}
}
return 0;
}