|Online Judge||Problem Set||Authors||Online Contests||User|
A market has a line of N trading posts selling sunflower seeds. Prospective buyers walk along the line, then at some moment stop and buy the seeds to nibble. Quality of the seeds does not differ substantially among the posts, so the only difference is in price and location of posts.
Before trying to enter this market as another seed seller, you have conducted a market research to find out how is the number of buyers influenced by these two factors. The research shows that most buyers follow the same pattern. They walk past some posts noticing and remembering the prices, then after passing K posts return to the one with the lowest price encountered, and make a purchase there, then leave the market. If there are several posts with the equal price, they choose the nearest one in the line.
For example, let us assume there are five posts with prices 37, 34, 34, 35, 33. If the buyer with K = 4 walks from the left to right, he sees seeds priced at 37, 34, 34, 35. At this moment, he decides he has seen enough, and goes back to the third post and buys seeds there. Although the second post has the same price as the third, it is a longer walk for the buyer to return there. If the same buyer would enter the line from the right end, he would see prices 33, 35, 34, 34, then stop and return to the fifth post.
The number of posts passed before the decision (K) is a function of buyer's greed and patience, and is obviously different for different buyers. The research yielded the average percentage BK of buyers for all values of K (1 <= K <= N, 0 <= BK <= 99, ∑1<=K<=NBK = 100).
You are to determine the optimal market strategy (i.e. the price and location of the new post which maximizes anticipated average income) under the assumptions that half of the clients walk in the direction from the first post to the Nth and another half - from the Nth post, to the first, and that they behave according to the pattern above.
The first line of the input contains the number of existing posts N (2 <= N <= 100). The second line contains N integers in range form 1 to 9999 - the prices for the posts. The third line contains N integers in range from 0 to 99 - the values of BK for each K. All numbers in a line are separated by spaces.
The output must contain two integers - L and P. L (1 <= L < N) is the number of the existing post after which the new one should be placed (You are not allowed to place your post first or last in the line). The second number P is the optimal price. If there is more than one optimal solution, you should choose the one with the minimal L, and between them - the one with minimal P.
5 37 34 34 35 33 10 20 30 30 10
Northeastern Europe 2001, Far-Eastern Subregion
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator