| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12431 | Min Sum of Inversions |
|
| 12432 | Find the Maximum Duplicate Number |
|
Description
Your mathematician friend get trouble again. He is trying to find the min sum of the inversion in the array, which is so samiliar to the problem we have taught him in homework. However, we can never leave friend in the lurch. Here is the problem:
Inversion : Let S be a sequence if i < j and S(i) > S(j), either the pair of places (i,j) or the pair of elements (S(i),S(j)) is called an inversion of S. Take [1,2,3,6,5,4] for example. (6,5) , (6,4) , (5,4) are inversion of the sequence [1,2,3,4,5,6]
Min sum of inversion: Calculate the sum of each inversion and find out the min sum. Take previous result (6,5), (6,4), (5,4) for example. Each sum of inversion will be 11, 10 and 9, then 9 is the min sum of inversion.
Note : If you are using visual studio, add #pragma warning(disable:4996) in the first line so that you can use scanf on your local machine.
Input
T
N_1 S_1
N_2 S_2
...
N_T S_T
T : The number of the testcase (1<= T<= 10)
N_i : The size of input sequence (2<= N_i < 1000)
S_i : The positive sequence with each element in the sequence is less than 1000000
Output
If there exists inversions, print out the min sum of inversions in the sequence
If there doesn't exists inversions, print out the string "No Inversion!"
(each output string must follow by a newline character)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a sequence containing N integers where each integer is between 1 and 1000(exclusive), prove that at least one duplicate number must exist. Assume that there could be multiple duplicate numbers, find the maximum value of duplicate one.
Note : If you are using visual studio, add #pragma warning(disable:4996) in the first line so that you can use scanf on your local machine.
Input
N
S
N is an integer, and 1<=N<10000.
S is a sequence. Each integer in it is between 1 and 1000(exclusive).
Output
Maximum duplicate number.
Remember change line in the end.