Max Delivery - Editorial

editorial
,
1

#Problem link:
[Practice] CodeChef: Practical coding for everyone
[Codeyssey] CodeChef: Practical coding for everyone

Author: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef
Editorialist: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef

DIFFICULTY: Easy-Medium
# PREREQUISITES: Math

Quick Approach to the question:

There are N Houses out of which 1 is our warehouse. We have N-1 houses left who want the delivery done. We have K points each point takes you from 1 house to the adjacent house.
Our job is to find the maximum number of house we can deliver to.
We can find houses on left&right of warehouse by simply
Left=w-1
Right=n-w
We need to take out two things first min-dist-on-one-side max-dist-on-one-side
min-dist-on-one-side=min(left,right)
max-dist-on-one-side=max(left,right)
Max points required to deliver to everyone can be found by
2Xmin-distance-of-one-side+max-dist-of-one side
The question depends on a few cases:

  1. If K is large enough to deliver to everyone
    i.e K>=2*mini+maxi
    then answer is n-1 that is all the houses.
  2. If K is greater than maxi but less than everyone than the approach is that we have to atleast deliver to all maxi houses i.e say we have 10 houses our warehouse is at 7th so maxi=6 and mini=3 and say
    K is =6 than best solution is to go and deliver from 7-6-5-4-3-2-1
    K=7 than also same
    K=8 than we can go from 7-8-7-6-5-4-3-2-1 hence answer=7
    i.e if K>=maxi than answer=maxi+((K-maxi)/(2))
    3) If K<maxi then ofcourse K is the answer because everytime we can go in the direction of maxi and get optimal solution……
    Keep In Mind to take long long for all input and variable since input can be upto 10^9.

#Solutions:

Editorialist’s & tester’s Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mod 1e9+7
#define For(i,n) for(int i=0;i<n;i++)
#define map map<int,int>
#define all(x) x.begin(),x.end()
void solve(){
ll n,w,k,l,r,mi,ma;
cin>>n>>w>>k;
l=w-1;
r=n-w;
mi=min(l,r);
ma=max(l,r);
if(k>=((mi2)+ma))
cout<<n-1<<endl;
else if(k>=ma&&k<((mi2)+ma))
cout<<(ma)+((k-ma)/(2))<<endl;
else
cout<<k<<endl;
}

int main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
int t;
cin>>t;
while(t–)
{
solve();}
}