Cho một mảng các số nguyên gồm N phần tử. Đếm số lượng các số khác nhau trong mảng

Ràng buộc: ~1 \leq N \leq 2.10^5~; ~1 \leq A[i] \leq 10^9~

input:

10
1 2 2 1 3 4 3 5 6 7

Output:

7

Nam có n viên gạch được đánh số từ 1 đến n. Các viên gạch có độ cứng lần lượt là a1, a2,..., an. Một viên gạch có độ cứng x nghĩa là Nam có thể chồng lên trên viên gạch đó tối đa x viên gạch khác, nếu chồng nhiều hơn thì viên gạch đó bị vỡ. Hỏi Nam có thể sắp được chồng gạch cao nhất là bao nhiêu?

Đầu vào:

Dòng đầu tiên là số nguyên n - là số viên gạch.

Dòng tiếp theo gồm n số nguyên a1, a2,.... an mỗi số cách nhau một khoảng trắng.

Ràng buộc: 1<=n<=10^5; 0 <= ai <= 10^6

Input:

4
1 2 3 4

Output:

4

Vào một buổi sáng anh Bo sắp xếp một đàn bò gồm n con bò để vắt sữa. Anh dự kiến là vào sáng hôm đó, con bò thứ có khả năng sẽ vắt được ai lít sữa. Tuy nhiên đàn bò của anh có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại trông thấy sợ quá nên sẽ bị giảm sản lượng mỗi con 1 lít sữa. Nếu vắt sữa con bò thứ nhất, n-1 con còn lại bị giảm sản lượng. Sau đó vắt sữa con bò thứ hai thì n-2 con còn lại bị giảm sản lượng... Bạn hãy giúp anh Bo tính xem thứ tự vắt sữa bò như thế nào để số lượng sữa vắt được là nhiều nhất nhé.

Đầu vào:

Dòng thứ nhất là số nguyên là số lượng con bò.

Dòng thứ hai gồm n số nguyên a1, a2...., an là sản lượng sữa của các con bò.

Ràng buộc: 1<=n<=10^5; 1<=a[i]<=10^6

Số nguyên xác định số lít sữa nhiều nhất mà anh Bo có thể vắt được.

Input

4
4 4 4 4

Output:

10

Ca sĩ nối tiếng Le Roi vừa nhận được các lời mời lưu diễn của n đoàn ca nhạc. Đoàn thứ i mời lưu diễn từ ngày ai đến ngày bi (ai, bi là các số nguyên, ai ≤ bi). Tuy nhiên tại một thời điểm, Le Roi chỉ có thể tham gia hát cho một đoàn duy nhất mà thôi. Với mong muốn đem lời ca tiếng hát của mình đến nhiều khán giả nhất, Le Roi quyết định sẽ chọn tham gia nhiều đoàn nhất có thể. Bạn hãy tính thử xem Le Roi nên chọn tham gia những đoàn nào để số lượng đoàn là nhiều nhất mà không bị trùng nhau về mặt thời gian.

Đầu vào:

Dòng thứ nhất là số nguyên n là số đoàn ca nhạc.

Trong n dòng tiếp theo, dòng thứ i gồm hai số ai, bi cách nhau một khoảng trắng là ngày bắt đầu và ngày kết thúc lưu diễn của đoàn thứ i.

Ràng buộc: 1<=n<=10^5; 1<=ai<=bi<=10^6

Đầu ra: Số nguyên xác định số lượng đoàn nhiều nhất mà Le Roi có thể tham gia.

Input:

6
3 8
9 12
6 10
1 4
2 7
11 14

Output:

3

Một dãy gồm n số nguyên không âm a1, a2,...., an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (n-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trằng đó để nhận được một biểu thức có giá trị lớn nhất. Ví dụ, với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1 +69 là biểu thức có giá trị lớn nhất. Yêu cầu: Cho dãy gồm n số nguyên không âm a1, a2..., an và số nguyên dương k, hãy tìm cách đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Đầu vào: Dòng đầu chứa hai số nguyên dương n, k; Dòng thứ hai chứa n số nguyên không âm a1, a2,..., an;

Ràng buộc: 1 <= k < n ≤ 10^5; 0 <= a[i] ≤ 10^6

In ra giá trị lớn nhất của biểu thức

Input:

5 3
10 1 3 9 8

Output:

29

Phân tích nhóm (phân nhóm, chia nhóm) là công việc phân chia các phần tử trong một tập hợp thành một hoặc nhiều nhóm mà trong đó các phần tử trong cùng một nhóm sẽ giống nhau hơn so với phần tử thuộc nhóm khác. Cho một tập N số nguyên dương và một sổ nguyên dương K, nhiệm vụ của bạn là đếm xem có bao nhiêu nhóm. Biết rắng 2 phần tử được xếp chung nhóm với nhau nếu như chênh lệch giữa chúng không vượt quá K.

Ví dụ: với tập N = 7 số nguyên dương: 2, 6, 1, 7, 3, 4, 9 và K = 1 thì ta sẽ có các mối quan hệ sau: 2 và 1 chung một nhóm (chênh lệch giữa chúng là 1, không vượt quá K) 2 và 3 chung một nhóm 6 và 7 chung một nhóm 3 và 4 chung một nhóm Vậy ta sẽ có 3 nhóm: {1, 2, 3, 4}, {6, 7} và (9}

Đầu vào:

Dòng đầu chứa 2 số nguyên dương N, K;

Dòng thứ hai chứa N số nguyên dương - các phần tử của tập hợp

Ràng buộc: 1<=N<=10^5; 1<=K<=10^6; Các phần tử trong tập hợp là số nguyên có trị tuyệt đối không vượt quá 10^6

Đầu ra: Kết quả của bài toán

Input:

7 1
2 6 1 7 3 4 9

Output:

3

Thành phố X có N thị trấn trên trục đường chính. Tọa độ của các thị trấn lần lượt là a[1],a[2], ..., a[N], các tọa độ này là phân biệt, không có 2 tọa độ nào trùng nhau. Chính quyền thành phố muốn xây dựng một tuyến buýt nhanh BRT để kết nối 2 thị trấn gần nhau nhất với nhau. Bạn hãy tính thử xem chiều dài của tuyển buýt này băng bao nhiêu? Và có bao nhiêu cặp thị trấn có tiềm năng giống nhau để xây dựng tuyến BRT này.

Định dạng đầu vào: Dòng đầu tiên là số nguyên N (N ≤ 1000000). Dòng tiếp theo gồm N số nguyên A[i]

Ràng buộc: N ≤ 1000000;-10^9 ≤ A[i] ≤ 10^9

Định dạng đầu ra: In ra 2 số nguyên C và D, lần lượt là khoảng cách ngắn nhất giữa 2 thị trấn và số lượng cặp thị trấn có cùng khoảng cách ngắn nhất này.

Input:

4
6 -3 0 4

Output:

2 1

Giải thích: Khoảng cách ngắn nhất giữa 2 thị trấn bằng 2 và có 1 cặp thị trấn thỏa mãn khoảng cách này

Cho hai dãy số nguyên dương A và B. Hãy trộn hai dãy với nhau sao cho dãy A được đưa vào các vị trí có chỉ số chẵn, dãy B được đưa vào các vị trí có chỉ số lẻ. Đồng thời, dãy A được sắp xếp tăng dần, còn dãy B được sắp xếp giảm dần. (Chú ý: chỉ số tính từ 0)

Định dạng đầu vào: Dòng đầu tiên ghi số n là số lượng phần tử của 2 dãy. Dòng tiếp theo ghi n số nguyên dương của dãy A. Dòng tiếp theo ghi n số nguyên dương của dãy B.

Ràng buộc: 1≤n≤10^5; 1 ≤ ai,bi ≤ 10^9

Định dạng đầu ra: In ra kết quả theo yêu cầu của bài toán

Input:

4
4 2 7 1
5 6 2 8

Output:

1 8 2 6 4 5 7 2

Cho dãy số A[] gồm có N phần tử, các phần tử trong mảng chỉ là 0 1 hoặc 2. Hãy sắp xếp các phần tử trong mảng theo thứ tự tăng dần.

Định dạng đầu vào: Dòng đầu tiên là số nguyên N. Dòng tiếp theo gồm N số nguyên A[i]

Ràng buộc: 1≤ N ≤ 10^7; 0 ≤ A[i] ≤ 2

Định dạng đầu ra: In ra mảng được sắp xếp tăng dần.

Input:

5
1 1 0 2 1

Output:

0 1 1 1 2

Cho mảng A[] gồm các số từ 0 đến 9. Nhiệm vụ của bạn là tìm tổng nhỏ nhất của hai số được tạo bởi các số trong mảng A. Chú ý, tất cả các số trong mảng A[] đều được sử dụng để tạo nên hai số. Chú ý nếu bạn tạo thành các số có số 0 đứng đầu thì bạn có thể loại bỏ các số 0 vô nghĩa đó.

Định dạng đầu vào: Dòng đầu tiên là số nguyên N. Dòng tiếp theo gồm N số nguyên A[i]

Ràng buộc: 1≤N≤30; 0≤A[i]≤9

Định dạng đầu ra: In ra kết quả của bài toán trên 1 dòng.

Input:

6
6 8 4 5 2 3

Output:

604

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

Đượ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

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

Cho một mảng A các số nguyên gồm N phần tử. In ra số xuất hiện nhiều nhất trong mảng và số lần xuất hiện. Nếu có nhiều số xuất hiện bằng nhau thì in ra số nhỏ hơn.

Ràng buộc: ~1 \leq N \leq 2.10^5~; ~-10^9 \leq A[i] \leq 10^9~

input:

5
1 2 2 1 3

Output:

1 2

Cho một dãy số gồm N số nguyên và một số nguyên dương K. Hãy tìm số nhỏ thứ K trong dãy số đó. Gợi ý: Sắp xếp dãy số tăng dần, sau đó lấy phần tử ở vị trí thứ K (nếu bắt đầu đếm từ 1).

Đầu vào:

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

Dòng thứ hai chứa N số nguyên.

Đầu ra:

In ra giá trị của số nhỏ thứ K.

Ràng buộc:

1 <= K <= N <= 1000

-10^6 <= A[i] <= 10^6

Ví dụ 1:

Input:

5 2 
9 1 3 5 2

Output:

2

Ví dụ 2:

Input:

6 3 
10 20 10 30 5 15

Output: 10