Bedao Mini Contest 16 - BINARY SORT

View as PDF
Submit solution
Points: 0.10
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
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.

Comments

Please read the guidelines before commenting.


  • 0
    L0ngg  commented on Nov. 3, 2023, 3:47 p.m.

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