1611 - The mell hell
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 335
Solved: 153
- Description
- In HUST,there are always many students go to the mell hall at the same time as soon as the bell rings. Students have to queue up for a meal ,and the queue is awalys long,So it takes much time.Suposse there are N people in a queue,each person has two characteristic value A and B(both of them are integers,read input for more details),the i-th person in the queue have to spend m(i)=A[1]*A[2]*…A[i-1]/B[i] minutes,Where A[i],B[i] is the i_th person’s value A,B.Notice that if the order of the queue changes,the waiting time one spend(that is,the value of m(i))may changes too. Of course,every student want to reduce the time he spend.
Apparently,it is impossible to make everyone satisfied,in this problem,we only need to minimize the waiting time of one who spend the longest time in the queue,that is,minimize Max{ m(1),m(2),…,m(n)}.You can change the order of the queue in anyway in order to complete this problem.
You are asked to output the original location in the queue of the person who will cost the longest time under optimal solution. Uniquity is insured by the given data.
- Input
- There are multiple test cases.
For each case, the first line contains one integer N(1≤N≤1000).
The second line contains N integers A[i].(0<A[i]<100000)
The third line contains N intergers B[i](0<B[i]<10).
(B[i] < 10 < A[i]*b[i]) (Please pay attention to the range, it is useful on this problem)
- Output
- You are asked to output the original location in the queue of the person who will cost the longest time under optimal solution.
Uniquity is insured by the given data.
- sample input
-
3 15 20 25 1 3 2
- sample output
-
2
- hint
- source
- The 7th(2012) ACM Programming Contest of HUST Problem Setter: Bingzhe Liu