Cho một mảng a gồm n phần tử là số nguyên. Sắp xếp sao cho số chẵn đứng trước, lẻ đứng sau, chẵn giảm dần, lẻ tăng dần

Đầu vào: Dòng đầu tiên là số lượng phần tử n, dòng tiếp theo là n phần tử của mảng

--

Ràng buộc: 1 <= n <= 1000000; 0 <= a[i] <= 1000000

Đầu ra: In ra mảng đã sắp xếp theo tiêu chí trên

Input:

10
1 2 10 9 6 5 8 7 4 3

Output:

10 8 6 4 2 1 3 5 7 9

Đại học Bang Berland đang tổ chức một buổi khiêu vũ trong lễ kỷ niệm 100500 năm thành lập! n các chàng trai và m cô gái đã bận rộn luyện tập các động tác nhảy múa. Cho biết rằng một số cặp nam và nữ sẽ được mời tham dự vũ hội. Tuy nhiên, kỹ năng khiêu vũ của các đối tác trong mỗi cặp khác nhau nhiều nhất là một đơn vị. Đối với mỗi chàng trai, chúng tôi biết kỹ năng nhảy của cậu ấy. Tương tự, đối với mỗi cô gái, chúng tôi biết kỹ năng khiêu vũ của cô ấy. Viết mã xác định số cặp lớn nhất có thế được hình thành từ n trai và m gái.

Định dạng đầu vào: Dòng đầu tiên chứa số nguyên n và m (1 <= n, m ≤ 10^5) - số chàng trai và số cô gái.

Dòng thứ hai chứa dãy a1, a2, ... , an (1 ≤ ai ≤ 10^5), trong đó ai là kỹ năng nhảy của chàng trai thứ i.

Dòng thứ ba chứa dãy b1, b2, ..., bm (1 ≤ bj ≤ 10^5), trong đó bj là kỹ năng nhảy của cô gái thứ j.

Ràng buộc: 1 <= n, m <= 10^5; 0 ≤ ai ≤ 10^5; 0 ≤ bj ≤ 10^5

Định dạng đầu ra: In một số duy nhất - số cặp tối đa được yêu cầu.

Input:

2 3
1 2
2 3 4

Output:

2

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

Lisa là bạn tin vào may mắn. Khi bạn ý làm contest thứ i trên HCNOJ bạn ý luôn có 2 giá trị L[i] và T[i] trong đó L[i] là chỉ số may mắn khi làm contest đó và T[i] là chỉ số quan trọng của contest (bằng 1 nếu contest thứ i là quan trọng và bằng 0 nếu contest thứ i là không quan trọng)

Nếu Lisa làm đúng contest thứ i thì chỉ số may mắn của bạn ý sẽ bị giảm đi 1 lượng L[i], nếu làm sai sẽ được cộng 1 lượng L[i]

Nếu Lisa làm sai không nhiều hơn k contest quan trọng thì chỉ số may mắn tối đa mà Lisa có sẽ là bao nhiêu?

Ràng buộc:

1 <= n <= 100

0 <= k <= n

1 <= Li <= 10^4

0 <= Ti <= 1

Đầu vào: Dòng đầu tiên gồm 2 số, số thứ nhất mô tả số lượng contest, số thứ 2 là k

Các dòng tiếp theo lần lượt là giá trị L[i] và T[i] của từng contest

Input:

6 3
5 1
2 1
1 1
8 1
10 0
5 0

Output:

29

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

Mark và Jane rất hạnh phúc sau khi có đứa con đầu lòng. Con trai của họ thích đồ chơi nên Mark muốn mua một ít. Có một số đồ chơi khác nhau nằm trước mặt cậu bé, được dán nhãn giá của chúng. Mark chỉ có một số tiền nhất định để chi tiêu và anh ấy muốn tối đa hóa số lượng đồ chơi mà mình mua được bằng số tiền này. Cho trước bảng giá đồ chơi và số tiền cần chi, hãy xác định số quà tối đa mà Mark có thể mua.

Đầu vào:

Dòng đầu tiên chứa hai số nguyên n và k là số lượng đồ chơi được định giá và số tiền Mark phải bỏ ra.

Dòng tiếp theo chứa n các số nguyên cách nhau bằng dấu cách là giá của từng đồ chơi

Ràng buộc:

1 <= n <= 10^5

1 <= k <= 10^9

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

Đầu ra: In ra số lượng đồ chơi tối đa Mark có thể mua được

Input:

7 50
1 12 5 111 200 1000 10

Output:

4

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

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

Cho mảng A gồm n các số nguyên dương. Bạn hãy thực hiện các thao tác sau đây:

• Sắp xếp các phần tử trong mảng A theo tần suất giảm dần, nếu 2 số có cùng tần suất thì số nào nhỏ hơn sẽ sắp xếp lên trước

• Sắp xếp các phần tử trong mảng A theo tần suất giảm dần, nếu 2 số có cùng tần suất thì số nào xuất hiện trước sẽ in ra trước

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

Input:

10
6 8 4 10 3 4 10 2 4 1

Output:

4 4 4 10 10 1 2 3 6 8 
4 4 4 10 10 6 8 3 2 1

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 01 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

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

Cho 2 dãy A và B đã sắp xếp tăng dần. Bạn hãy thực hiện trộn 2 dãy A và B thành 1 dãy C cũng sắp xếp tăng dần.

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

Input:

5
1 3 5 6 9
3
2 7 8

Output:

1 2 3 5 6 7 8 9

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 mảng các số nguyên gồm N phần tử. Tìm khoảng cách (độ chênh lệch) nhỏ nhất của 2 phần tử bất kỳ trong mảng.

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

input:

5
1 2 7 5 6

Output:

1

Cho một mảng A các số nguyên gồm N phần tử. Sắp xếp các phần tử trong mảng A theo tổng chữ số trong một phần tử tăng dần. Nếu 2 số có cùng tổng chữ số thì số nào nhỏ hơn in ra trước.

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

input:

7
100 101 1 2 400 4 202

Output:

1 100 2 101 4 202 400

Cho mảng A có N phần tử là các số nguyên. Hãy sắp xếp lại mảng theo giá trị tuyệt đối tăng dần. Lưu ý nếu phần tử đã đứng ở đúng vị trí thì không được sắp xếp lại.

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

Input:

5
1 -3 2 -5 -1

Output:

1 -1 2 -3 -5

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

Có n đứa trẻ muốn đi đu quay và nhiệm vụ của bạn là tim một chiếc thuyền Gondola cho mỗi đứa trẻ. Mỗi chiếc Gondola có thể có một hoặc hai người trong đó và ngoài ra, tổng trọng lượng của một chiêc Gondola không được vượt quá x. Bạn biết cân năng của mọi đứa trẻ, vậy số lượng thuyền Gondola tôi thiếu cần thiết cho trẻ em là bao nhiêu?

Định dạng đầu vào: Dòng nhập dầu tiên chửa hai số nguyên n và x: số dứa trẻ và trọng lượng tối đa cho phép. Dòng tiếp theo chứa n số nguyên p1, p2,.., pn: trọng lượng của mỗi đứa trẻ

Ràng buộc: 1 <= n ≤ 2.10^5; 1 <= X ≤ 10^9; 1 <= pi <= x;

Định dạng đầu ra: In một số nguyên: số lượng thuyền Gondola tối thiếu.

Input:

4 10
7 2 3 9

Output:

3

Có n người nộp đơn và m căn hộ miễn phí. Nhiệm vụ của bạn là phân phối các căn hộ sao cho càng nhiều người đăng ký sẽ nhận được căn hộ càng tốt. Mỗi người nộp đơn có một kích thước căn hộ mong muốn và họ sẽ chấp nhận bất kỳ căn hộ nào có diện tích gần với kích thước mong muốn.

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

Dòng nhập đầu tiên có ba số nguyên n, m và k: số người đăng ký, số căn hộ và chênh lệch tối đa cho phép.

Dòng tiếp theo chứa n số nguyên a1, a2,.., an: diện tích căn hộ mong muốn của mỗi người đăng ký. Nếu kích thước mong muốn của người nộp đơn là x, người đó sẽ chấp nhận bất kỳ căn hộ nào có kích thước từ x - k đến x + k.

Dòng cuối cùng ghi m số nguyên b1, b2,..., bm: diện tích từng căn hộ.

Ràng buộc: 1 <= n, m ≤ 10^5; 0 <= k ≤ 10^9; 1 <= ai, bi ≤ 10^9

In một số nguyên: số người nộp đơn sẽ nhận được một căn hộ.

Input:

4 3 5
60 45 80 60
30 60 75

Output:

2

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ố?

Đị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