HSPC14B - Sắp xếp
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
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 <= 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 ≤ a i ≤ 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
Example
Input: 3 3 2 1 3 4 1 3 2 -1 -10 Output: 1 3
- Người up: beo_chay_so
- Nguồn bài: HSPC 2014