HSG THPT TPHCM 2023 - Thuật Toán Sắp Xếp

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem source:
Kỳ thi Học sinh giỏi THPT TPHCM 2023
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Sắp xếp là một trong những thuật toán phổ biến nhất trong khoa học máy tính. An vừa được giới thiệu các thuật toán sắp xếp và biết rằng thuật toán sắp xếp nhanh (Quick Sort) có độ phức tạp trung bình là ~O(n \log{n})~. Tuy nhiên An vẫn muốn sáng tạo một thuật toán sắp xếp mới và xem thử liệu nó có tốt hơn Quick Sort. Xét một mảng ~n~ số nguyên, mỗi phần tử có giá trị từ ~1~ đến ~n~ và mỗi giá trị chỉ xuất hiện một lần trong mảng. Thuật toán này sẽ sắp xếp mảng trên trong ~n~ bước như sau:

  • Bước 1: phần tử có giá trị ~1~ sẽ được chuyển đến vị trí ~1~ bằng cách liên tiếp hoán đổi vị trí với phần tử liền kề với nó.

  • Bước 2: phần tử có giá trị ~n~ sẽ được chuyển đến vị trí ~n~ bằng cách như bước ~1~.

  • Bước 3: phần tử có giá trị ~2~ sẽ được chuyển đến vị trí ~2~ bằng cách tương tự.

  • Bước 4: phần tử có giá trị ~n - 1~ sẽ được chuyển đến vị trí ~n - 1~ bằng cách tương tự.

  • Và cứ thể tiếp tục đến bước ~n~.

Tổng quát hơn, ở bước lẻ, An sẽ chọn phần tử có giá trị nhỏ nhất chưa được sắp xếp và di chuyển phần tử này đến vị trí đúng của nó. Ở bước chẵn An sẽ chọn phần tử có giá trị lớn nhất chưa được sắp xếp và di chuyển phần tử này đến vị trí đúng của nó.

Yêu cầu: Viết chương trình cho biết số lần hoán đổi vị trí các phần tử tại mỗi bước của thuật toán trên.

Input

  • Dòng đầu tiên chứa một số nguyên ~n~ cho biết số lượng phần tử của mảng.

  • Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên ~a_i~ ~(1 \leq a_i \leq n)~ cho biết giá trị của phần tử thứ ~i~ trong mảng. Các giá trị ~a_i~ không lặp lại.

Output

  • Gồm ~n~ số nguyên, số thứ ~i~ cho biết số lần hoán đổi vị trí các phần tử ở bước thứ ~i~ của thuật toán. Mỗi số ghi trên một dòng.

Scoring

Subtask Điểm Giới hạn
1 ~50\%~ ~n \leq 1000~
2 ~20\%~ ~n \leq 10000~
3 ~30\%~ ~n \leq 100000~

Sample Input 1

7
5
2
6
7
3
1
4

Sample Output 1

5
2
1
2
1
1
0

Comments

Please read the guidelines before commenting.


There are no comments at the moment.