Bedao Mini Contest 16 - BINARY SORT

Xem dạng PDF

Gửi bài giải


Điểm: 0,10
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy ~a~ gồm ~n~ số nguyên ~a_0,a_1,\dots,a_{n-1}~ ~(0\leq a_i\leq 1)~. Ta sắp xếp lại dãy ~a~ theo thứ tự tăng dần bằng thuật toán Bubble sort được mô tả như bên dưới.

sorted = false 
while (sorted == false):
    sorted = true
    for i = 0 to n - 2:
    if a[i + 1] < a[i]:
        swap(a[i + 1], a[i])
        sorted = false

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

Hãy cho biết số lần lệnh ~swap~ được dùng.

Input

  • Dòng đầu chứa số nguyên ~n~ là độ dài của dãy số ~(1\leq n \leq 10^6)~.

  • Dòng thứ hai chứa ~n~ số nguyên ~a_0,a_1,\dots,a_{n-1}~ ~(0\leq a_i \leq 1)~

Output

  • Gồm một số nguyên duy nhất là kết quả của bài toán

Sample Input 1

5
1 0 1 0 1

Sample Output 1

3

Notes

  • ~30\%~ số test có ~n \leq 3000~

  • ~70\%~ số test còn lại không có ràng buộc gì thêm.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    L0ngg  đã bình luận lúc 3, Tháng 11, 2023, 15:47

    đề này na ná câu 1 của đề HSG TPHCM năm 2022 - 2023 thì phải :D