Cho mảng A có N phần tử và mảng B có M phần tử, hãy in ra các phần tử có trong cả mảng A và mảng B, nếu trùng nhau chỉ in 1 lần. Nếu không có phần tử nào trùng lặp thì in ra NONE

Ràng buộc: ~0 < N, M \leq 10^6~, ~-10^6 < A[i], B[i] \leq 10^6~

Input 01:

3 4
1 2 3
3 4 5 6

Output 01:

3

Input 02:

6 4
1 2 3 4 5 6
3 4 5 6

Output 02:

3 4 5 6

Input 03:

3 4
1 2 2
3 4 5 6

Output 03:

NONE

Vanya đi bộ vào ban đêm dọc theo một con đường thẳng dài có độ dài l, được thắp sáng bởi n chiếc đèn lồng. Xét hệ trục tọa độ với điểm đầu của đường phố tương ứng với điểm 0 và điểm cuối của nó tương ứng với điểm l. Khi đó đèn lồng thứ i ở điểm ai. Đèn lồng chiếu sáng tất cả các điểm trên đường phố cách nó nhiều nhất là d, trong đó d là một số dương, chung cho tất cả các đèn lồng. Vanya tự hỏi: bán kính ánh sáng tối thiểu d mà những chiếc đèn lồng phải có để thắp sáng cả con phố?

Lưu ý: Phải sắp xếp lại tọa độ theo thứ tự tăng dần

Định dạng đầu vào:

Dòng đầu tiên chứa hai số nguyên n, l (1 ≤ n ≤ 10^5, 1 ≤ l ≤ 10^9) - số lượng đèn lồng và chiều dài đường phố tương ứng. Dòng tiếp theo chứa n số nguyên ai (0 ≤ ai ≤ l). Nhiều đèn lồng có thể được đặt tại cùng một điểm. Đèn lồng có thế nằm ở cuối phố.

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

Định đạng đầu ra: In ra bán kính chiếu sáng tối thiểu, làm tròn lấy 2 chữ số sau phần thập phân

Input:

3 8
2 4 5

Output:

3.00

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

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

Priyanka làm việc cho một công ty đồ chơi quốc tế vận chuyển bằng container. Nhiệm vụ của cô là xác định cách kết hợp các đơn hàng để vận chuyển với chi phí thấp nhất. Cô ấy có một danh sách trọng lượng các món đồ. Công ty vận chuyển có yêu cầu tất cả các mặt hàng được xếp trong container phải có trọng lượng nhỏ hơn hoặc bằng 4 đơn vị cộng với trọng lượng của mặt hàng có trọng lượng nhỏ nhất. Tất cả các mặt hàng đáp ứng yêu cầu đó sẽ được vận chuyển trong một container.

Xác định số lượng container nhỏ nhất có thể được ký hợp đồng để vận chuyển các mặt hàng dựa trên danh sách trọng lượng đã cho là bao nhiêu?

Ví dụ: Có những món đồ có trọng lượng w = [1,2,3,4,5,10,11,12,13]. Điều này có thể được chia thành hai container chứa là [1,2,3,4,5] và [10,11,12,13]. Mỗi container chứa sẽ chứa các đơn hàng có trọng lượng giữa đơn hàng có trọng lượng lớn nhất và nhỏ nhất không vượt quá 4

Đầu vào:

Dòng đầu tiên chứa số nguyên là số lượng đơn hàng cần vận chuyển.

Dòng tiếp theo chứa n các số nguyên được phân tách bằng dấu cách w[1], w[2], ..., w[n] biểu thị trọng lượng của các đơn hàng.

Ràng buộc:

1 <= n <= 10^5

1 <= w[i] <= 10^4

Đầu ra: Trả về giá trị nguyên của số container Priyanka phải ký hợp đồng để vận chuyển tất cả đồ chơi.

Input:

8
1 2 3 21 7 12 14 21

Output:

4

Jim's Burgers có một lượng lớn khách hàng đang đói bụng. Các đơn đặt hàng có sự khác nhau về thời gian cần thiết để chuẩn bị chúng. Mỗi đơn hàng của khách có 2 giá trị là thời gian đặt hàng (thứ tự đặt hàng) và thời gian chuẩn bị.

Đầu vào:

Dòng đầu tiên chứa số nguyên là số lượng khách hàng.

Mỗi dòng tiếp theo chứa hai số nguyên được phân tách bằng dấu cách, số thứ tự và thời gian chuẩn bị cho từng đơn hàng.

Ràng buộc:

1 <= n <= 10^3

1 <= i <= n

1 <= order[i], prep[i] <= 10^6

Đầu ra: Một dòng mã số khách hàng được phân tách bằng dấu cách (hãy nhớ rằng khách hàng được đánh số từ 1 đến n) mô tả trình tự khách hàng nhận được đơn hàng. Nếu hai hoặc nhiều khách hàng nhận được đơn hàng cùng lúc, hãy in số của họ theo thứ tự tăng dần.

Input 01:

3
1 3
2 3
3 3

Output 01:

1 2 3

Input 02:

5
8 1
4 2
5 6
3 1
4 3

Output 02:

4 2 5 1 3

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

Sắp xếp dãy số theo thứ tự tăng dần của tổng các chữ số. Nếu tổng các chữ số bằng nhau, số nào có giá trị nhỏ hơn sẽ đứng trước.

Dữ liệu vào:

Dòng 1: N.

Dòng 2: N số nguyên dương A[i].

Dữ liệu ra:

Dãy số đã sắp xếp.

Ràng buộc:

1 <= N <= 10^5

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

Ví dụ:

Input:

4
12 30 100 23

Output:

100 12 30 23

Giải thích: Tổng chữ số lần lượt là 1, 3, 3, 5. Số 12 và 30 có cùng tổng là 3 nhưng 12 < 30.

Hãy sắp xếp dãy số theo thứ tự tăng dần của chữ số tận cùng. Nếu chữ số tận cùng bằng nhau, số lớn hơn đứng trước.

Dữ liệu vào:

Dòng 1: Số nguyên dương N.

Dòng 2: N số nguyên A[i].

Dữ liệu ra:

Dãy số đã sắp xếp.

Ràng buộc:

1 <= N <= 10^5

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

Ví dụ:

Input:

5
15 32 104 22 9

Output:

32 22 104 15 9

Cho dãy số nguyên dương A. Hãy sắp xếp dãy số này sao cho tổng các chữ số của từng số tăng dần. Nếu tổng các chữ số bằng nhau, số nào có giá trị gốc nhỏ hơn sẽ đứng trước.

Dữ liệu vào:

Dòng 1: Số nguyên dương N.

Dòng 2: N số nguyên A[i].

Dữ liệu ra:

Dãy số sau khi sắp xếp.

Ràng buộc:

1 <= N <= 1000

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

Ví dụ:

4 
12 30 100 23

Output:

100 12 30 23

Cho dãy số nguyên dương A. Hãy sắp xếp dãy số sao cho số dư của chúng khi chia cho 3 tăng dần. Nếu hai số có cùng số dư khi chia cho 3, số nào nhỏ hơn sẽ đứng trước.

Dữ liệu vào:

Dòng 1: Số nguyên dương N.

Dòng 2: N số nguyên A[i].

Dữ liệu ra:

Dãy số sau khi sắp xếp.

Ràng buộc:

1 <= N <= 10^5

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

Ví dụ:

Input:

5 
10 2 5 6 1

Output:

6 1 10 2 5

Cho dãy số A. Hãy đưa các số nguyên tố ra đầu dãy (tăng dần), các số không phải nguyên tố về cuối dãy (tăng dần).

Dữ liệu vào:

Dòng 1: N.

Dòng 2: N số nguyên dương A[i].

Dữ liệu ra:

Dãy số đã sắp xếp.

Ràng buộc:

1 <= N <= 1000

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

Ví dụ:

Input:

5
4 3 7 10 2

Output:

2 3 7 4 10

Cho mảng A có N phần tử là các số nguyên đã được sắp xếp theo thứ tự tăng dần. Hãy viết các hàm với độ phức tạp O(logN):

1. Tìm vị trí xuất hiện đầu tiên của phần tử X trong mảng, nếu không có in ra -1

2. Tìm vị trí xuất hiện cuối cùng của phần tử X trong mảng, nếu không có in ra -1

3. Tìm vị trí xuất hiện đầu tiên của phần tử >=X trong mảng, nếu không có in ra -1

4. Tìm vị trí xuất hiện đầu tiên của phần tử >X trong mảng, nếu không có in ra -1

5. Tìm số lần hiện của phần tử X trong mảng sử dụng kết quả trong hàm 1 và 2

Ràng buộc: ~1 \leq N \leq 10^6~; ~0 \leq A[i] \leq 10^6~

Input:

10 1100
10 1000 2172 2921 3400 4185 4639 6096 6244 9102

Output:

-1
-1
2
2
0

Cho mảng a gồm n phăn tử và số nguyên dương k. Đếm số lượng cặp số ai, aj (i != j) có tổng nhỏ hơn k.

Định dạng đầu vào: Dòng thứ 1 là số lượng phần tử trong mảng và số nguyên dương k; Dòng thứ 2 là n phần tử trong mảng

Ràng buộc: 2<=п<=10^6; 1<=k<=10^6; 0<=a(i)<=10^6;

Định dạng đầu ra: In ra số lượng cặp số có tổng bằng k

Input:

4 5
2 2 2 2

Output:

6

Cho mảng a gồm n phăn tử và số nguyên dương k. Đếm số lượng cặp số ai, aj (i != j) có tổng lớn hơn k.

Định dạng đầu vào: Dòng thứ 1 là số lượng phần tử trong mảng và số nguyên dương k; Dòng thứ 2 là n phần tử trong mảng

Ràng buộc: 2<=п<=10^6; 1<=k<=10^6; 0<=a(i)<=10^6;

Định dạng đầu ra: In ra số lượng cặp số có tổng bằng k

Input:

4 5
2 3 4 5

Output:

5