Xếp sách

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
datnvt
Dạng bài
Điểm: 220 Thời gian: 1.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

\(\color{blue}{Tade}\) là một thủ thư làm việc rất chuyên cần ở thư viện \(Abcdef\). Hôm nay, \(\color{blue}{Tade}\) được \(Big Boss\) giao nhiệm vụ sắp xếp lại đống sách mới được gửi đến. Khổ nỗi, \(Boss\) lại yêu cầu \(\color{blue}{Tade}\) sắp xếp \(10^7\) đống sách theo thứ tự không giảm trong vòng \(1s\), mà trong thời gian đó anh ta chỉ có thể sắp xếp được \(10^6\) quyển thôi.

\(\color{blue}{Tade}\) đành phải nhờ đến các bạn lqdcoder giúp đỡ, các bạn hãy giúp anh ấy nhé!

Input

  • Dòng đầu chứa một số tự nhiên \(N (1\le N\le 10^7)\) là số sách mà Tade cần phải sắp xếp.

  • Dòng tiếp theo chứa \(N\) số tự nhiên \(a_i (1\le a_i\le 100)\), là số thứ tự của mỗi quyển sách. Lưu ý, hai quyển sách có thể có cùng một số thứ tự.

Output

  • Một dòng chứa \(N\) số là các số thứ tự được sắp xếp không giảm của \(N\) quyển sách đó.

Example

Test 1

Input 
6
1 5 4 2 3 4
Output 
1 2 3 4 4 5

Bình luận


  • 1
    scratch_huykhanh    9:46 a.m. 14 Tháng 8, 2024
    Solution

    Với mỗi số nhập vào, tăng giá trị của nó thêm 1 trong mảng đếm phân phối (tạm gọi mảng đếm phân phối là \(D\)).
    For từ \(1\) đến \(100\) (Vì A[i] \(\leq\) \(100\)), với mỗi giá trị i có \(D[i]\)>0, in ra i \(D[i]\) lần (Ví dụ: \(D[3]\) = 5 (Xuất hiện 5 lần) thì in ra 3 3 3 3 3)

    \(AC code (Python):\) 
    limit = 101 #Vì mảng của python bắt đầu từ 0
D = [0]*(limit)
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    D[A[i]]+=1
for i in range(1,limit):
    print((str(i)+' ')*D[i],end="")
    • 19 bình luận nữa