| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1425 | Problem A - Minimum Scalar Product |
|
| 1426 | PB - Bribe the Prisoners |
|
Description
You are given two vectors v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn.
Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.
Input
The first line of the input file contains integer number T - the number of test cases. For each test case, the first line contains integer number n. The next two lines contain n integers each, giving the coordinates of v1 and v2 respectively.
T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000
Output
For each test case, output a line
Case #X: Y
where X is the test case number, starting from 1, and Y is the minimum scalar product of all permutations of the two given vectors.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.
All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to his other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.
Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.
Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.
Input
The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is formatted as
P Q
where P is the number of prison cells and Q is the number of prisoners to be released.
This will be followed by a line with Q distinct cell numbers (of the prisoners to be released), space separated, sorted in ascending order.
1 ≤ N ≤ 100
Q ≤ P
Each cell number is between 1 and P, inclusive.
1 ≤ P ≤ 10000
1 ≤ Q ≤ 100
Output
For each test case, output one line in the format
Case #X: C
where X is the case number, starting from 1, and C is the minimum number of gold coins needed as bribes.