MYQ6 - Serve The Street
Shree is a very ambitious person and wants to start a new company "RAM COURIER SERVICE" in the country of Thuvax. He plans to open his first office in the Main Street of Thuvax to serve only the people of this street. The Main Street is an inclined road consisting of N buildings spaced out unevenly(building 1 at lowest level and building N at highest level). The distance between adjacent buildings are known to Shree.
The delivery costs incurred by him for various deliveries are calculated as follows:
To deliver a package of weight 'w' to a building downhill at a distance 'd' from the office, Shree spends w*d*1 units of money.
To deliver a package of weight 'w' to a building uphill at a distance 'd' from the office, Shree spends w*d*2 units of money.
To deliver a package of non-zero weight to his own building, Shree spends 10 units of money irrespective of the weight of the package.
Shree being an astute businessman wants to choose one of these buildings for his new office so that the total delivery cost incurred by him is minimum.
Help Shree choose the building for his new office.
The first line of the input consists of number of test cases t(1<=t<=20)
The first line of each test case consists of a single number N(1<=N<=10^6) which is the number of buildings in the main street.
The next line contains N integers representing the weight to be delivered at ith (1<=i<=N) building (0<=w[i]<=100).
The last line contains N-1 integers where the ith (1<=i<=N-1) integer represents the distance between i and i+1 th building(1<=d[i]<=100).
Output a single line for each test case containing two integers separated by a space.
The first integer is the minimum delivery cost and the next integer is the building number where the office should be placed in order to incur that cost.
If more than one building has the same minimum cost, print the building labelled with the smallest number.
1 2 3 4 5
1 1 1 1 Output: 30 4
did in O(n) take care for weight as 0 that case me 1 WA.Last edit: 2017-01-27 10:59:04
I won't lie ,took me 2 hours to do this in O(n)[ i know i know :( ] but then AC in one go :)
Stuck on this problem , getting a TLE with O(n) ?
is O(n^2) a bad time limit?
don't read till EOF.. I have got AC and those getting WAs might want to check when n=1 as a special case.
read till EOF ...Last edit: 2012-08-10 09:56:28
take care of long long too, in addition to the comments below..Last edit: 2012-08-05 20:07:18
that 10 cost me 7 wa ...
Yes, delivering package of weight zero ALWAYS costs 0.
What is the cost for delivering zero weight package in the building itself? zero?