ZOJ Problem Set - 2951
Because of the war, the relative peace of the Frostwolves has been challenged. The Frostwolves, now led by the Orc Shaman Drek'Thar, choose to keep the goods in some warehouses.
The warehouses are arranged in a circle, and goods can be transported to the two neighboring warehouses. For example, goods in the i-th warehouse can be transported to the i+1-st warehouse or the i-1-st warehouse, and the goods in the first warehouse can be transported to the last warehouse and vice versa. Every part of neighboring warehouse has a distance, and the longer the distance is, the more gold will be cost to transport. You can assume that if the distance is x, the transportation cost of one unit goods will also be x unit of gold (x need not be an integer). Each warehouse has an integer attribute, which indicates its priority level. Higher priority level means the warehouse should keep more goods. For example, if the i-th warehouse has A goods, and the priority level is a, while the j-th warehouse has B goods, and the priority level is b, then A/B should be equal to a/b. Given the original states of the warehouses (how much goods in each warehouse), the priority attribute of each warehouse, and the distance of the i-th warehouse to the i+1-st warehouse, you must output the minimum transportation cost to keep the priority attributes right.
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 50) which is the number of test cases. And it will be followed by T consecutive test cases.
For each test case, first is an integer N (2 <= N <= 2000), which indicates the number of the warehouses. Then N integers follow, which indicate the goods each warehouse contains. Then N integers follow, which indicate the priority levels of each warehouse. Then N integers follow, the i-th of which indicates the distance between the i-th warehouse and the next warehouse (the last distance is between the N-th warehouse and the first warehouse).
Results should be directed to standard output. The output of each test case should be a single floating number, which is the minimum transportation cost to keep the priority attribute right (accurate to two fractional digits).
1 3 2 1 3 1 1 1 3 1 3
Author: CHEN, Zhengguang
Source: Zhejiang University Local Contest 2008