Market Place
Time Limit: 1 Second Memory Limit: 32768 KB
Special Judge
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, sum of BK = 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.
Input
The first line of the input file 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.
Process to the end of file.
Output
The output file 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, anyone is OK.
Sample Input
5 37 34 34 35 33 10 20 30 30 10
Sample Output
3 33Submit
Source: Northeastern Europe 2001, Far-Eastern Subregion