Beginner
1. Consecutive Prime Sum2. Alpha Numeric Sorting3. Longest Progressive Sequence4. Divine Divisor5. Forest Fire6. Minimum Distance7. Saving for a rainy day8. Online Communities Even Groups9. Coin Distribution10. Bank Compare11. Counting Rock Samples12. Collecting Candies13. Game Of Primes14. Kth Largest Factor15. Jumble With Numbers16. Philand Coins17. Reverse Gear18. String Rotation19. The Vita Sum20. Mountain Peak Sequence21. LAZY STUDENT22. LOGIC PYRAMID23. Super ASCII String Checker24. Min Product Array25. String Of Brackets26. Exchange Of Digits27. Marathon Winner28. Common Steps29. Swayamvar30. Digit Pairs31. Dole Out Cadbury32. Petrol Pump33. Grooving Monkeys34. Death BattlePetrol Pump
LEVEL:Beginner
Description
A big group of students, starting a long journey on different set of vehicles need to fill petrol in their vehicles.
As group leader you are required to minimize the time they spend at the petrol pump to start the journey at the earliest. You will be given the quantity of petrol (in litres) that can be filled in each vehicle. There are two petrol vending machines at the petrol pump. You need to arrange the vehicles in such a way that they take shortest possible time to fill all the vehicles and provide the time taken in seconds as output. Machine vends petrol @ 1litre/second.
Assume that there is no time lost between switching vehicles to start filling petrol.
Input Format
First line will provide the quantity of petrol (separated by space) that can be filled in each vehicle.
Output Format
Shortest possible time to fill petrol in all the vehicles.
1 2 3 4 5 10 11 3 6 16
31
25 30 35 20 90 110 45 70 80 12 30 35 85
335
10 3 5 7
13
Login to see Discussion
Approach
This should be solved using Dynamic Programming.
Step-i)create a method min_time which takes arr and n as argument
Step-ii)get the sum of the array elements
Step-iii)create a 2 d array of size sum+1 and n+1
Step-iv)for i in range of value 0 to n+1 assing true to dp[i][0]
Step-v)for i in range of value 1 to sum+1 assign false to dp[0][i]
Step-vi)assign sum+1/2 to half
Step-vii)now for i in range of value 1 to n+1 follow below step
Step-viii)for j in range of value 1 to sum+1 follow below step
Step-ix)update dp[i][j] to dp[i-1][j] and if arr[i-1] <= j then perform dp[i][j] = dp[i][j] or dp[i-1][j-arr[i-1]]
Step-x)for j in range of half to sum-1 if dp[n][j] is true return j else return sum
Step-xi)now take necessary inputs and print the output
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution