Cho một dãy số nguyên A gồm N phần tử. Hãy đếm xem trong dãy có bao nhiêu giá trị khác nhau.

Gợi ý: Sau khi sắp xếp, các phần tử bằng nhau sẽ đứng cạnh nhau.

Đầu vào:

Dòng đầu tiên chứa số nguyên dương N.

Dòng thứ hai chứa N số nguyên A[i].

Đầu ra:

Một số nguyên duy nhất là số lượng các giá trị khác nhau trong dãy.

Giới hạn:

1 <= N <= 10^5

|A[i]| <= 10^9

Ví dụ:

Input:

5 
1 2 1 3 2

Output:

3

Input:

4 
10 10 10 10

Output:

1

Cho N số nguyên trên trục số. Hãy tìm khoảng cách nhỏ nhất giữa hai số bất kỳ trong dãy số đã cho. (Khoảng cách giữa x và y là giá trị tuyệt đối |x - y|).

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương N (N >= 2).

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

In ra khoảng cách nhỏ nhất tìm được.

Giới hạn:

2 <= N <= 10^5

0 <= A[i] <= 10^9

Ví dụ 1:

Input:

4 
1 5 3 19

Output:

2

Ví dụ 2:

Input:

3 
1 100 10

Output:

9

Tí có một số tiền là M đồng. Cửa hàng đồ chơi có N món đồ, món thứ i có giá là A[i]. Tí muốn mua được nhiều món đồ nhất có thể với số tiền M. Hãy tính xem Tí có thể mua được tối đa bao nhiêu món đồ.

Dữ liệu vào:

Dòng đầu tiên chứa hai số N và M.

Dòng thứ hai chứa N số nguyên A[i] là giá của các món đồ chơi.

Dữ liệu ra:

Số lượng món đồ tối đa Tí có thể mua.

Giới hạn:

1 <= N <= 10^5

1 <= M <= 10^14

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

5 10 
3 1 4 2 5

Output:

4

Ví dụ 2:

Input:

3 5 
10 20 30

Output: 0

Cho N thanh gỗ có độ dài khác nhau được cho bởi dãy số A. Hãy chọn ra 3 thanh gỗ để ghép thành một hình tam giác sao cho chu vi của tam giác đó là lớn nhất. Nếu không thể ghép được tam giác nào, in ra 0. (Điều kiện tạo tam giác: tổng 2 cạnh bất kỳ luôn lớn hơn cạnh còn lại).

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương N.

Dòng thứ hai chứa N số nguyên A[i] là độ dài các thanh gỗ.

Dữ liệu ra:

In ra chu vi lớn nhất tìm được.

Giới hạn:

3 <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

4 
2 3 4 10

Output:

9

Ví dụ 2:

Input:

3 
1 2 10

Output:

0

Cho một dãy số A gồm N phần tử. Sau khi sắp xếp dãy số, các phần tử có giá trị bằng nhau sẽ nằm liền kề nhau. Hãy tìm độ dài của dãy con liên tiếp dài nhất chứa các phần tử có giá trị bằng nhau.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Một số nguyên là độ dài của dãy con liên tiếp dài nhất chứa các giá trị bằng nhau.

Giới hạn:

1 <= N <= 10^5

|A[i]| <= 10^9

Ví dụ 1:

Input:

6 
1 1 2 2 2 3

Output:

3

Ví dụ 2:

Input:

5 
1 2 3 4 5

Output:

1

Cho dãy số nguyên A gồm N phần tử (có thể chứa số âm). Hãy tìm 3 số trong dãy sao cho tích của chúng là lớn nhất. In ra giá trị tích đó. Gợi ý: Tích lớn nhất có thể tạo từ 3 số lớn nhất, hoặc 2 số nhỏ nhất (số âm có trị tuyệt đối lớn) nhân với 1 số lớn nhất (số dương).

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương N.

Dòng thứ hai chứa N số nguyên A[i]. Dữ liệu ra:

Một số nguyên duy nhất là tích lớn nhất của 3 số.

Giới hạn:

3 <= N <= 10^5

|A[i]| <= 10^6 (Kết quả có thể lên tới 10^18, hãy dùng kiểu long long)

Ví dụ 1:

Input:

4 
-10 -10 1 2

Output:

200

Ví dụ 2:

Input:

3 
-5 -2 -1

Output:

-10

Lớp học có N bạn nam và N bạn nữ. Bạn nam thứ i có chỉ số IQ là A[i], bạn nữ thứ i có chỉ số IQ là B[i]. Giáo viên muốn ghép N cặp (mỗi cặp gồm 1 nam và 1 nữ) sao cho tổng độ chênh lệch IQ của các cặp là nhỏ nhất. Độ chênh lệch IQ của một cặp (x, y) là giá trị tuyệt đối |x - y|. Hãy tính tổng chênh lệch nhỏ nhất đó.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương N.

Dòng thứ hai chứa N số nguyên A[i] (IQ nam).

Dòng thứ ba chứa N số nguyên B[i] (IQ nữ).

Dữ liệu ra:

Tổng độ chênh lệch nhỏ nhất.

Giới hạn:

1 <= N <= 10^5

1 <= A[i], B[i] <= 10^9

Ví dụ 1:

Input:

3 
1 5 10 
2 4 20

Output:

12

Ví dụ 2:

Input:

2 
1 100 
100 1

Output:

0

Đội tuyển kéo co cần chọn ra K bạn từ N học sinh đăng ký. Mỗi học sinh có một chỉ số sức mạnh là A[i]. Để đội tuyển mạnh nhất, huấn luyện viên muốn tổng sức mạnh của K bạn được chọn là lớn nhất. Hãy tính tổng sức mạnh lớn nhất đó.

Dữ liệu vào:

Dòng đầu chứa hai số nguyên N và K.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Tổng sức mạnh lớn nhất tìm được.

Giới hạn:

1 <= K <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

5 3 
10 20 5 8 12

Output:

42

Ví dụ 2:

Input:

4 1 
1 2 3 4

Output:

4

Nhân dịp lễ, siêu thị có chương trình khuyến mãi "Mua 3 tặng 1". Cụ thể, khi mua 3 món hàng bất kỳ, khách hàng sẽ được miễn phí món hàng có giá thấp nhất trong 3 món đó. Tí chọn mua N món hàng. Hãy giúp Tí sắp xếp thứ tự thanh toán (hoặc nhóm các món hàng lại) sao cho số tiền phải trả là ít nhất.

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i] là giá của các món hàng.

Dữ liệu ra:

Số tiền tối thiểu Tí phải trả.

Giới hạn:

1 <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

4 
20 30 10 50

Output:

90

Ví dụ 2:

Input:

7 
1 2 3 4 5 6 7

Output:

21

Cô giáo muốn chọn ra K bạn học sinh trong lớp gồm N bạn để lập thành một nhóm múa. Mỗi bạn có chiều cao A[i]. Để đội hình đẹp, cô muốn chênh lệch giữa bạn cao nhất và bạn thấp nhất trong nhóm K bạn này là nhỏ nhất. Hãy tìm độ chênh lệch nhỏ nhất đó.

Dữ liệu vào:

Dòng đầu chứa hai số N và K.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Độ chênh lệch nhỏ nhất (Min(Max - Min) của tập con K phần tử).

Giới hạn:

2 <= K <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

5 3 
10 100 30 20 25

Output:

10

(Giải thích: Chọn 20, 25, 30. Chênh lệch 30 - 20 = 10)

Ví dụ 2:

Input:

6 3 
1 15 4 10 8 20

Output:

6

(Giải thích: Chọn 4, 8, 10. Chênh lệch 10 - 4 = 6)

Trong một cuộc bầu cử lớp trưởng, các ứng viên được đánh số. Mảng A gồm N phần tử ghi lại phiếu bầu, trong đó A[i] là mã số của ứng viên được chọn trong phiếu thứ i. Hãy tìm mã số của ứng viên nhận được nhiều phiếu bầu nhất. Nếu có nhiều người cùng số phiếu cao nhất, in ra người có mã số nhỏ nhất.

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Mã số của ứng viên chiến thắng.

Giới hạn:

1 <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

6 
1 2 2 1 3 1

Output:

1

Ví dụ 2:

Input:

4 
5 2 5 2

Output:

2

(Giải thích: 2 và 5 đều xuất hiện 2 lần, nhưng 2 nhỏ hơn 5 nên in 2)

Cho dãy số nguyên dương A gồm N phần tử. Hãy sắp xếp lại dãy số này sao cho tổng: S = A[0]x1 + A[1]x2 + ... + A[N-1]xN đạt giá trị lớn nhất (với chỉ số mảng tính từ 0). In ra giá trị S đó (Lấy dư cho 10^9 + 7 nếu cần, nhưng ở bài này giới hạn nhỏ nên cứ in số long long).

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Giá trị tổng lớn nhất S. Giới hạn:

1 <= N <= 10^5

1 <= A[i] <= 10^6 (Lưu ý: Kết quả có thể lên tới 10^18, dùng long long)

Ví dụ 1:

Input:

3 
2 1 3

Output:

14

(Giải thích: Sắp xếp thành 1, 2, 3. Tổng = 1x1 + 2x2 + 3x3 = 1+4+9 = 14)

Ví dụ 2:

Input:

2
10 10

Output: 30

(Giải thích: 10x1 + 10x2 = 30)

Một danh sách đầy đủ phải chứa các số từ 1 đến N. Tuy nhiên người ta nhập thiếu mất 1 số, nên dãy chỉ còn N-1 số. Hãy tìm số bị thiếu đó.

Dữ liệu vào:

Dòng đầu chứa số nguyên N (dãy hiện tại có N-1 số).

Dòng thứ hai chứa N-1 số nguyên, các số đều khác nhau và nằm trong khoảng [1, N].

Dữ liệu ra:

Số bị thiếu.

Giới hạn:

2 <= N <= 10^5

Ví dụ 1:

Input:

5 
1 2 4 5

Output:

3

Ví dụ 2:

Input:

4 
4 1 3

Output:

2

Cho dãy số A gồm N phần tử. Hãy đếm xem có bao nhiêu cặp chỉ số (i, j) sao cho i < j và A[i] = A[j].

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Số lượng cặp phần tử bằng nhau.

Giới hạn:

1 <= N <= 10^5

|A[i]| <= 10^9

Ví dụ 1:

Input:

5 
2 1 2 2 3

Output:

3

(Giải thích: Các cặp giá trị 2 là (vị trí 0, 2), (0, 3), (2, 3))

Ví dụ 2:

Input:

3 
1 2 3

Output:

0

Tí có N thanh gỗ với độ dài khác nhau. Tí muốn ghép các thanh gỗ này thành các hình chữ nhật. Mỗi hình chữ nhật cần 2 cặp cạnh bằng nhau (ví dụ 2 thanh dài L và 2 thanh dài W). Tí muốn chọn ra 4 thanh gỗ để ghép thành 1 hình chữ nhật sao cho diện tích của nó là lớn nhất có thể. Nếu không thể ghép được, in ra 0.

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Diện tích hình chữ nhật lớn nhất.

Giới hạn:

4 <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

8 
2 5 2 5 5 2 2 10

Output:

10

Giải thích: Có 4 thanh 2 và 3 thanh 5. Ta có thể ghép hình chữ nhật 2x5. Diện tích 10. Thanh 10 ko có cặp nên bỏ.

Ví dụ 2:

Input:

5 
1 2 3 4 5

Output:

0

Cho 2 dãy số A và B đều có N phần tử. Bạn được phép hoán đổi vị trí các phần tử trong mỗi dãy tùy ý. Nhiệm vụ của bạn là làm sao để tổng S = A[0]xB[0] + A[1]xB[1] + ... + A[N-1]xB[N-1] là nhỏ nhất có thể.

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa dãy A.

Dòng thứ ba chứa dãy B.

Dữ liệu ra:

Giá trị nhỏ nhất của S.

Giới hạn:

1 <= N <= 10^5

|A[i]|, |B[i]| <= 10^6 (Kết quả dùng long long)

Ví dụ 1:

Input:

3 
1 2 3 
4 5 6

Output:

28

Giải thích: Sắp A tăng dần 1 2 3, B giảm dần 6 5 4. Tổng: 16 + 25 + 34 = 6+10+12 = 28. Nếu để nguyên là 14+25+36 = 32

Ví dụ 2:

Input:

2 
10 20 
-5 5

Output:

-50

Giải thích: 10x5 + 20x(-5) = 50 - 100 = -50

Trong dãy số A gồm N phần tử, mọi số đều xuất hiện đúng 2 lần, ngoại trừ một số duy nhất chỉ xuất hiện đúng 1 lần. Hãy tìm số đó.

Dữ liệu vào:

Dòng đầu chứa số nguyên lẻ N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Số duy nhất xuất hiện 1 lần.

Giới hạn:

1 <= N <= 2*10^5 + 1

|A[i]| <= 10^9

Ví dụ 1:

Input:

5 
1 2 1 3 2

Output:

3

Ví dụ 2:

Input:

1 
100

Output:

100

Cho N số nguyên được nhập dưới dạng chuỗi (do số rất lớn, không lưu vừa kiểu int hay long long). Hãy sắp xếp các số này theo thứ tự tăng dần.

Dữ liệu vào:

Dòng 1: N.

Dòng 2: N chuỗi số.

Dữ liệu ra:

Các chuỗi số đã sắp xếp.

Ràng buộc:

1 <= N <= 1000

Độ dài mỗi chuỗi số <= 100

Ví dụ:

Input:

3
10 2 100

Output:

2 10 100

Lớp học của HCN gồm có n học sinh. HCN cầm một danh sách bao gồm tên, ngày sinh và điểm trung bình của các bạn trong lớp. Là lớp trưởng, HCN được giáo viên tín nhiệm giao công việc sắp xếp điểm các bạn theo thứ tự, Tuy nhiên, bạn đã biết HCN chăm chỉ thế nào, nên đã tự giác đi làm thay bạn ý luôn...

Đầu vào:

• Dòng đầu tiên chứa số nguyên dương n - số lượng học sinh trong lớp HCN (n ≤ 60).

• n dòng tiếp theo, môi dòng chứa ba thông tin: Tên (không dấu), ngày sinh và điếm trung bình (là một số thực không vượt quá 10).

• Dữ liệu đám bảo không có 2 bạn nào cùng điểm.

Đầu ra: Gồm n dòng, theo thứ tự điểm từ thấp nhất đến cao nhất, gồm tên và điểm của từng học sinh (cách nhau một khoảng trắng).

Input:

3
Lan 18/9/2006 8.8
An 11/3/2006 9.1
TDZ 10/12/2006 8.0

Output:

TDZ 8.0
Lan 8.8
An 9.1

Được nghỉ hè nhưng không biết làm gì, HCN liền lên ý tưởng lập một hiệu sách dạo ngoài đường.

HCN dự định bán n quyển sách cũ của mình, quyển sách thứ i có giá là c. Tuy nhiên, sợ do ế khách, HCN đề ra một chương trình ưu đãi "mua 3, tặng 1".

Mỗi khách mua ba quyển sẽ được tặng một quyển có giá rẻ nhất trong ba quyển đó. Mỗi khách hàng có thể mua bao nhiêu sách cũng được và có thể trả số tiền khác nhau phụ thuộc vào việc chọn các nhóm bộ ba sách.

Ví dụ, một khách hàng lấy các quyển sách có giá 10, 3, 2, 4, 6, 4, 9. Nếu các quyển sách được sắp thành các nhóm: (10, 3, 2), (4, 6, 4) và (9) thì khách hàng ấy sẽ được tặng cuốn sách có giá là 2 trong nhóm một, 4 trong nhóm hai và không có quyến sách nào được tặng trong nhóm ba vì nhóm này chỉ có 1 quyển.

Hãy giúp HCN tính số tiền ít nhất có thể thu được khi bán hết n quyển sách đó, vì cậu trốn quá nhiều tiết Toán rồi...

Input:

• Dòng đầu tiên chưa số nguyên dương n (n ≤ 10^5).

• Dòng tiếp theo chứa n số nguyên dương c1, c2, c3, ..., cn tương ứng với giá tiền mỗi quyển sách (c ≤ 10^5).

Output:

In ra số tiền thu được ít nhất có thể khi bán hết n quyến sách.

Input:

4
3 2 3 2

Output:

8

Input:

6
6 4 5 5 5 5

Output:

21

Kiểm tra xem mảng cho trước có tồn tại 2 số nguyên liên tiếp hay không, nếu có in ra YES, ngược lại in ra NO.

Ví dụ:

Input:

5
8 14 99 15 20

Output:

YES