PROBLEM LINK: Contest Practice
Author: Baban Gain
Editorialist: Baban Gain
DIFFICULTY:
SIMPLE
PREREQUISITES:
Array
PROBLEM:
Chef wants to set up restaurants between Berhampore and different cities.
Given a distance D between the city and Berhampore, You need to find the minimum no. of restaurants chef needs to build.
However, distance between two consecutive restaurants should not be more than K kilometers.
Also, to maximize profit, Chef must set up restaurants on every major cities in between.
Consider Chef already have a restaurant in berhampore. And roads between different cities do not overlap.
EXPLANATION:
Add 0 at front of the distance array and D ( destination distance at the end of array ).
Now for i = 1 to end of array,
count += ceil ( (arr[i] - arr[i-1]) /K ).
By the formula, we can find minimum no. of restaurants to be built between two major cities. and repeat it for all the cities.
Note : ceil function rounds up to next integer. Because Chef cannot build say 6.2 restaurants but he needs to build 7 instread. If he builds 6, distance would go more than K kilometers
AUTHOR’S SOLUTION:
Author’s solution can be found here.