Sắp xếp - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Sắp xếp không giảm	100 (p)	1.0s	256M
2	Sắp xếp không tăng	100 (p)	10.0s	256M
3	Số lớn thứ k	100 (p)	1.0s	256M
4	Số nhỏ thứ k	100 (p)	1.0s	256M
5	Yugioh	100 (p)	1.0s	256M
6	Biến đổi số	100 (p)	1.0s	640M
7	LMHT	100 (p)	1.0s	256M

1. Sắp xếp không giảm

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một dãy gồm \(n\) số nguyên dương \(A_1, A_2,…, A_n\). (\(N ≤ 10^4, A_i ≤ 10^9\)). Hãy in ra dãy số sau khi sắp xếp dãy số tăng dần (\(A_i ≤ A_{i+1}\)).

Input

Dòng đầu chứa số \(n\),
Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2,…, A_n\).

Output

Một dòng chứa dãy số đã sắp xếp tăng dần.

Example

Test 1

Input

6
91 451 43 3 451 54

Output

3 43 54 91 451 451

2. Sắp xếp không tăng

Điểm: 100 (p) Thời gian: 10.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một dãy gồm \(n\) số nguyên dương \(A_1, A_2,…, A_n\). (\(N ≤ 10^4, A_i ≤ 10^9\)). Hãy in ra dãy số sau khi sắp xếp dãy số giảm dần (\(A_i ≥ A_{i+1}\)).

Input

Dòng đầu chứa số \(n\),
Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2,…, A_n\).

Output

Một dòng chứa dãy số đã sắp xếp giảm dần.

Example

Test 1

Input

6
91 451 43 3 451 54

Output

451 451 91 54 43 3

3. Số lớn thứ k

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2,…, A_N\).(\(N ≤ 10^4, A_i ≤ 10^9\)) và số \(K\) (\(K ≤ N\)). Hãy in ra số lớn thứ \(K\) trong dãy.

Input

Dòng đầu chứa số \(N, K\),
Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2,…, A_N\).

Output

Một dòng chứa dãy số lớn thứ \(K\) trong dãy.

Example

Test 1

Input

6 2    
91 451 43 3 452 54

Output

4. Số nhỏ thứ k

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

5. Yugioh

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Yugi có \(N\) lá bài, lá bài thứ \(i\) có sức mạnh như sau:

Nếu \(A_i \ge 0\) máu của Yugi sẽ được cộng thêm \(A_i\).

Nếu \(A_i <0\) máu của Kaiba sẽ trừ đi \(|A_i|\).

Tuy nhiên, Yugi luôn thích tấn công nên anh ta muốn trừ máu Kaiba nhiều nhất có thể.

Hãy cho biết Yugi có thể trừ Kaiba nhiều nhất là bao nhiêu khi sử dụng nhiều nhất \(m\) lá bài

Input

Dòng đầu chứa số \(n, m (1 \leq m \leq n \leq 10000)\)
Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2,…, A_n (-10000 \leq A_i \leq 10000)\).

Output

Số máu Kaiba bị trừ.

Example

Test 1

Input

 5 3 
-6 0 35 -2 4

Output

6. Biến đổi số

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Vào một buổi sáng, rất tình cờ Nam nhìn thấy một số nguyên dương \(N\) trên đường từ nhà đến trường. Vì Nam rất thích số \(30\) nên Nam muốn biến đổi số \(N\) thành số \(M\) có dạng là số lớn nhất và là bội của số \(30\) bằng cách thay đổi vị trí của các chữ số trong số \(N\) mà Nam nhìn thấy.

Bạn hãy hỗ trợ Nam bằng cách viết chương trình để tìm số \(M\) (nếu nó tồn tại).

Input

Gồm một dòng duy nhất chứa số nguyên \(N\) (\(N\) có tối đa là \(10^5\) chữ số).

Output

In ra số \(M\) tìm được. Nếu không tồn tại \(M\) thì in ra \(-1\).

Example

Test 1

Input

Output

Test 2

Input

Output

Test 3

Input

3333333333333333333333333333

Output

-1

7. LMHT

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong Liên minh huyền thoại có \(N\) vị tướng, vị tướng thứ \(i\) có \(2\) sát thương vật lý và sát thương phép.

Vị tướng thứ \(i\) được cho là mạnh hơn vị tướng thứ \(j\) nếu có sát thương vật lý mạnh hơn.

Hai vị tướng có cùng sát thương vật lý thì vị tướng mạnh hơn sẽ có sát thương phép lớn hơn.

Hãy cho biết chỉ số sát thương vật lý và phép của vị tướng mạnh thứ \(m\).

Input

Dòng đầu chứa số \(n, m (1 \leq m \leq n \leq 10000)\)
\(n\) dòng, mỗi dòng chứa 2 số nguyên \(A_i(\)vật lý\(),B_i(\)phép\() (0 \leq A_i,B_i \leq 10000)\).

Output

Chỉ số sát thương

Example

Test 1

Input

Output

1  3