Sắp xếp

View as PDF

Submit solution

Points: 1.82 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
HSPC 2014
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy số nguyên ~a_1~, ~a_2~, ..., ~a_N~ và số nguyên ~M~. Xét thuật toán đưa ~M~ số nhỏ nhất về đầu dãy như sau

for i := 1 to M do
    for j := i + 1 to N do
        if a[i] > a[j] then
            swap(a[i], a[j])

Trong đó ~swap~ là hàm đổi giá trị của ~2~ biến cho nhau.

Cho số nguyên ~M~ và dãy số nguyên ~a_1~, ~a_2~, ..., ~a_N~. Hãy đếm số lần thực hiện hàm ~swap~ sau khi thuật toán kết thúc.

Input

Gồm nhiều bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng ~1~: Hai số nguyên dương ~N~ và ~M~ với ~0 < N~, ~M \le 10^{5}~.

Dòng ~2~: ~N~ số nguyên thể hiện dãy ~a~, mỗi số cách nhau ít nhất ~1~ dấu cách. ~- 10^{9} \leq a_i \leq 10^{9}~.

Output

Ứng với mỗi test, in ra ~1~ dòng duy nhất chứa số lần thực hiện hàm ~swap~ theo yêu cầu bài toán.

Sample Input

3 3
2 1 3
4 1
3 2 -1 -10

Sample Output

1
3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.