[ad_1]
Given an array arr[] of measurement N, and integers Ok and D, consisting of breakpoints in journey, the duty is to search out the space coated after the final breakpoint with at most Ok price following the given circumstances:
- Place to begin is 0
- 1 unit distance is roofed for 1 price.
- For transferring D steady distance there may be an additional price of D i.e., complete price turns into D*1 + D = 2D.
Be aware: If N = 0 meaning there isn’t any breakpoint and beginning is from 0.
Examples:
Enter: arr[] = {17, 12, 18}, Ok = 28, D = 8
Output: 2
Clarification: Motion from 0 to eight. Coated distance price = 8*1 + 8 = 16
Motion from 8 to 12 as 12 is a break level. Value = 12 – 8 = 4. Complete price = 16 + 4 = 20.
Motion from 12 to 17. Value = 17 – 12 = 5. Complete price = 20 + 5 = 25.
Motion from 17 to 18. Value = 18 – 17 = 1. Complete Value = 26.
Remaining price = 2.
So additional distance that may be coated after final breakpoint(18) = 2.Enter: arr[] = {}, Ok = 100, D = 8
Output: 52
Clarification: Motion from 0 to eight. Distance = 8. Value = 8*1 + 8 = 16. Complete = 16
Motion from 8 to 16. Distance = 8. Value = 8*1 + 8 = 16. Complete = 32.
Motion from 16 to 24. Distance = 8. Value = 8*1 + 8 = 16. Complete = 48.
Motion from 24 to 32. Distance = 8. Value = 8*1 + 8 = 16. Complete = 64.
Motion from 32 to 40. Distance = 8. Value = 8*1 + 8 = 16. Complete = 80.
Motion from 40 to 48. Distance = 8. Value = 8*1 + 8 = 16. Complete = 96.
Motion from 48 to 52. Distance = 4. Value = 4*1 = 4. Complete = 100.
Distance coated after final breakpoint (no breakpoint right here)= 52.
Strategy: The given downside may be solved based mostly on the next mathematical remark:
Distance between two consecutive breakpoints X and Y is (X – Y).
The variety of instances D consecutive actions are made = ground((X – Y)/D).
The associated fee for these consecutive actions is 2*D * ground((X-Y)/D).
Say M price is paid to achieve the final breakpoint.
Then the additional D consecutive distances that may be coated is ground((Ok – M)/2*D).
The associated fee for that is D* ground((Ok – M)/2*D). If the remaining price is > D then solely D extra distance may be coated.
Comply with the steps to unravel the issue:
- First examine for Edge Case N = 0
- If N!=0 then kind the given breakpoints.
- Calculate the space from the 1st level to 0th level.
- Traverse the array from i = 1 to N – 1.
- Calculate the space between arr[i] and arr[i-1].
- Calculate the price to cowl this distance (say Depend).
- If, Ok<= Depend, return 0
- Calculate the additional distance through the use of the above remark:
- Res = D*(( Ok – Depend) / (2*D) ) (variety of instances consecutive D distances coated)
- Rem = (Ok – Depend) % (2*D) (Remaining price)
- If, Rem >= D && Rem <=(2*D-1) then Rem = D
- Return, Res + Rem as the ultimate additional distance coated.
Beneath is the implementation of the above method:
C++
|
|
Time Complexity: O(N * logN)
Auxiliary Area: O(1)
[ad_2]
