Cho một mảng A các số nguyên có N phần tử, sử dụng hàm tìm kiếm nhị phân có sẵn để tìm kiếm giá trị X nhập từ bàn phím

Dòng đầu tiên nhập N và X

Dòng tiếp theo nhập N giá trị của mảng A

In ra FOUND nếu tìm thấy và NOT FOUND nếu không tìm thấy

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

Input:

5 6
3 5 6 9 13

Output:

FOUND

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ử. Nhiệm vụ của bạn là tìm giá trị nhỏ nhất (phải thuộc mảng A) lớn hơn Ai (i = 0, 1, 2,, n-1). Đưa ra ký tự _ nếu Ai không có phần từ lớn hơn nó. Ví dụ với mảng A = (13, 6, 7, 12) ta có kết quả là (_ , 7, 12, 13).

Định dạng đầu vào: Dòng đầu tiên đưa vào n là số phần tử của mảng A; Dòng kế tiếp đưa vào n số A[i] của mảng; các số được viết cách nhau một vài khoảng trống.

Ràng buộc: 1 <= N <= 10^5; 1 ≤ A[i] <= 10^5.

Định dạng đầu ra: Đưa ra kết quả trên 1 dòng

Input:

9
6 3 9 8 10 2 1 15 7

Output:

7 6 10 9 15 3 2 _ 8

Cho mảng A gồm N phần tử. Sử dụng hàm có sẵn tìm vị trí đầu tiên của phần tử lớn hơn hoặc bằng X.

Dòng đầu tiên nhập N và X

Dòng tiếp theo nhập N giá trị của mảng A

In ra vị trí nếu tìm thấy, nếu không tìm thấy thì in ra N.

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

Input 01:

10 6
3 5 6 6 6 6 9 10 11 13

Output 01:

2

Vị trí đầu tiên trong mảng lớn hơn hoặc bằng 6 là vị trí có chỉ số là 2 (có giá trị là 6)

Input 02:

10 14
3 5 6 6 6 6 9 10 11 13

Output 02:

10

Cho một mảng A nguyên gồm N phần tử đã sắp xếp tăng dần, hãy tìm chỉ số của phần tử x xuất hiện đầu tiên trong mảng, ví dụ mảng 1, 3, 4, 5, 5, 5, 6, 7. Nếu tìm số x = 5 thì số 5 xuất hiện đầu tiên sẽ có chỉ số 3, in ra chỉ số này. Nếu không tìm thấy in ra -1.

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

Input 01:

8 5
1 3 4 5 5 5 6 7

Output 01:

3

Input 02:

7 -3
-3 -3 -1 4 5 6 7

Output 02:

0

Input 03:

6 10
1 3 4 5 6 7

Output 03:

-1

Cho một mảng A nguyên gồm N phần tử, hãy tìm chỉ số của phần tử xuất hiện cuối cùng trong mảng, ví dụ mảng 1, 3, 4, 5, 5, 5, 6, 7. Nếu tìm số 5 thì số 5 xuất hiện cuối cùng sẽ có chỉ số 5, chỉ số này được in ra. Nếu không tìm thấy thì in ra -1

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

Input 01:

8 5
1 3 4 5 5 5 6 7

Output 01:

5

Input 02:

7 -3
-3 -3 -1 4 5 6 7

Output 02:

1

Input 03:

6 10
1 3 4 5 6 7

Output 03:

-1

Cho một mảng A gồm N số nguyên chưa được sắp xếp. Có Q truy vấn được đưa ra, mỗi truy vấn yêu cầu bạn kiểm tra một số nguyên X và đếm xem X xuất hiện bao nhiêu lần trong mảng A.

Gợi ý: Vì số lượng truy vấn Q rất lớn, việc dùng vòng lặp quét toàn bộ mảng cho mỗi câu hỏi sẽ bị quá thời gian. Các em cần sắp xếp mảng trước, sau đó vận dụng Tìm kiếm nhị phân (hoặc các hàm lowerbound, upperbound trong C++) để tối ưu hóa thời gian tìm kiếm.

Đầu vào:

• Dòng thứ nhất chứa hai số nguyên dương N và Q lần lượt là số lượng phần tử của mảng và số lượng truy vấn.

• Dòng thứ hai chứa N số nguyên A[i] cách nhau bởi khoảng trắng.

• Q dòng tiếp theo, mỗi dòng chứa một số nguyên X tương ứng với một truy vấn.

Ràng buộc:

• 1 <= N, Q <= 10^5

• -10^9 <= A[i], X <= 10^9

Đầu ra:

In ra Q dòng, mỗi dòng là số lần xuất hiện của X tương ứng với từng truy vấn.

Ví dụ:

Input 01:

5 3
5 1 4 6 3
3
6
10

Output 01:

1
1
0

Input 02:

6 4
1 3 1 4 1 7
1
2
4
7

Output 02:

3
0
1
1

Cho một mảng A nguyên gồm N phần tử đã sắp xếp tăng dần, hãy tìm chỉ số của phần tử xuất hiện đầu tiên trong mảng, ví dụ mảng 1, 3, 4, 5, 5, 5, 6, 7. Nếu tìm số 5 thì số 5 xuất hiện đầu tiên sẽ có chỉ số 3, chỉ số này được in ra. Nếu không tìm thấy thì in ra -1

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

Input 01:

8 5
1 3 4 5 5 5 6 7

Output 01:

3

Input 02:

7 -3
-3 -3 -1 4 5 6 7

Output 02:

0

Input 03:

6 10
1 3 4 5 6 7

Output 03:

-1

Cho dãy A đã sắp xếp tăng dần. Với mỗi truy vấn X, hãy tìm số nhỏ nhất trong dãy A mà có giá trị lớn hơn hoặc bằng X. Nếu không có số nào thỏa mãn, in ra "Khong".

Dữ liệu vào:

Dòng 1: N và Q.

Dòng 2: Dãy A.

Q dòng tiếp theo: Mỗi dòng là một số X.

Dữ liệu ra:

Giá trị tìm được hoặc "Khong".

Ràng buộc:

1 <= N, Q <= 10^5

Ví dụ:

Input:

5 2 
1 4 5 8 9 
6 
10

Output:

8 
Khong

Cho dãy A đã sắp xếp tăng dần. Với mỗi truy vấn X, tìm số nhỏ nhất trong dãy A mà lớn hơn hẳn X (lớn hơn chặt).

Dữ liệu vào:

Dòng 1: N và Q.

Dòng 2: Dãy A.

Q dòng tiếp theo: Mỗi dòng là số X.

Dữ liệu ra:

Giá trị tìm được hoặc "Khong".

Ràng buộc:

1 <= N, Q <= 10^5

Ví dụ:

Input:

5 2 
1 4 5 5 9 
5 
9

Output:

9 
Khong

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 bằng k.

Gợi ý: Sắp xếp mảng tăng dẫn sau đó với mỗi phần tử a[i] trong mảng tìm xem trong đoạn [i + 1, n - 1] có bao nhiêu phần tử có giá trị là k - a[i], bằng cách tìm vị trí đầu tiên và vị trí cuối cùng của phần tử có giá trị là k - a[i] => Số lượng

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

Output:

6

Cho mảng A gồm N phần tử và số X. Nhiệm vụ của bạn là tìm cặp phần tử A[i] - A[j] = X.

Nếu tồn tại A[i] - A[j] = X đưa ra 1, ngược lại đưa ra -1.

Input Format: Dòng thứ nhất là cặp số N, X; Dòng tiếp theo là N số A(i] là các phần tử của mảng A.

Ràng buộc: ~1 ≤ N ≤ 10^5~; ~1 ≤ X, A[i] ≤ 10^{5}~.

Input 01:

5 4
1 2 3 4 5

Output 01:

1

Giải thích: Cặp số có hiệu bằng 4 là 5 và 1

Input 02:

5 5
1 2 3 4 5

Output 02:

-1

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

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ột dãy A gồm N số nguyên a1, a2, a3, ..., aN đã được sắp xếp tăng dần. Bạn cần trả lời Q truy vấn sau:

Cho 3 số l, r, x, có bao nhiêu số có giá trị x trong dãy con al, a(l+1), a(l+2), ..., ar?

Đầu vào:

Dòng đầu tiên gồm duy nhất số nguyên N (N <= 10^6) - kích thước mảng.

Dòng thứ hai gồm N số nguyên ai (0 <= ai <= 10^9).

Dòng thứ ba gồm số truy vấn Q (Q <= 10^5) - số truy vấn.

Q dòng tiếp theo mỗi dòng gồm 3 số l,r,x (0 <= l <= r <= n-1).

Đầu ra:

Q dòng cho biết có bao nhiêu số có giá trị x trong dãy con al, a(l+1), a(l+2), ..., ar? ở mỗi truy vấn.

Input:

7
1 2 3 3 4 4 5
2
0 6 5
0 5 4

Output:

1
2

Bạn được cho biết thời gian đến và đi của n khách hàng trong một nhà hàng. Số lượng khách hàng có mặt tại cửa hàng ở 1 thời điểm nhiều nhất là bao nhiêu?

Định dạng đầu vào: Dòng nhập dầu tiên có số nguyên n là số lượng khách hàng. Sau đó, có n dòng mô tả khách hàng. Mỗi dòng có hai số nguyên a và b là thời gian đến và đi của một khách hàng. Bạn có thể cho răng tất cả thời gian đến và đi là khác nhau.

Ràng buộc: 1 <= n, m ≤ 2.10^5; 1 ≤ a, b ≤ 10^9

Định dạng đầu ra: In một số nguyên là số lượng khách hàng tối đa.

Input:

3
5 8
2 4
3 9

Output:

2

Trong một liên hoan phim, n bộ phim sẽ được chiếu. Bạn biết thời gian bắt dầu và kết thúc của mỗi bộ phim. Số lượng phim tối đa bạn có thế xem toàn bộ là bao nhiều? Biết rằng nếu thời gian kết thúc của bộ phim trước bằng hoặc nhỏ hơn thời gian bắt đầu của bộ phim sau thì bạn có thể xem cả 2 phim này.

Định dạng đầu vào: Dòng nhập đầu tiên có số nguyên n là số lượng phim. Sau đó, có n dòng mô tả các bộ phim. Mỗi dòng có hai số nguyên a và b là thời gian bắt đầu và kết thúc của một bộ phim.

Ràng buộc: 1 < n, m <= 2.10^5; 1 ≤ a, b ≤ 10^9

Định dạng đầu ra: In một số nguyên là số lượng phim tối đa.

Input:

3
3 5
4 6
2 4

Output:

2

Một buổi tối nọ, HCN tổ chức một bữa tiệc ở quán cà phê của mình.

Có n người xuất hiện, người thứ i có chiều cao h;. Những bữa tiệc thì không thế thiếu đi những hoạt động vui vẻ nên HCN quyết định ghép các cặp hai người cho một trò chơi team-building của mình. Vì không muốn để cho các cặp đôi trông quá chênh lệch về chiều cao, HCN đã đưa ra yêu cầu:

Người thứ i và người thứ j (i ‡ j) có thể ghép cặp được với nhau nếu 90% * hj ≤ hi ≤ hj. Hai cách ghép cặp (i, j) và cặp (j, i) được coi là một.

Với số lượng người tham dự nhỏ HCN có thể dễ dàng tính ra được số cách ghép các cặp khác nhau, nhưng do đã lỡ tay mời quá nhiều người nên việc tính toán của HCN trở nên khó khăn hơn. Hãy giúp HCN làm công việc này nhé.

Đầu vào:

• Dòng đầu tiên chứa số nguyên dương n - Số người ở bữa tiệc (1 ≤ n ≤ 10^5).

• Dòng tiếp theo chứa n số nguyên dương h1, h2, h3, ..., hn tương ứng với chiều cao từng người (hi ≤ 10^9).

Đầu ra:

In ra số cách chọn các cặp khác nhau.

Input:

6
100 89 90 101 91 99

Output:

11

Cho hai số nguyên dương L và R.

Yêu cầu: Tìm số nguyên dương M (L ≤ M < R) để chênh lệch giữa tổng các số nguyên liên tiếp từ L đến M và tổng các số nguyên liên tiếp từ M + 1 đến R là nhỏ nhất.

Dữ liệu vào bàn phím: Gồm hai số nguyên dương L và R (L < R ≤ 10^9).

Kết quả in ra: Gồm một số nguyên duy nhất là số M thoả mãn.

Input:

2 7

Output:

5

Tổng từ 2 đến 5 là: 14. Tổng từ 6 đến 7 là: 13

Chênh lệch là: 1

Lưu ý: Mỗi số nguyên cách nhau một dấu cách.

• Có 60% số test: L < R ≤ 10^3;

• Có 40% số test còn lại: L < R ≤ 10^9

Nhân dịp kênh YouTube của HCN được 100 triệu subscribers, chủ kênh HCN giấu tên quyết định mở một cuộc giveaway lớn nhất trong lịch sử. Cụ thể, sẽ có n subscribers được chọn và mỗi subscriber này sẽ nhận được một mã số ai và một hộp quà có giá trị là bi (1≤i≤n).

Kênh YouTube HCN được thành lập để truyền tải những thông điệp nhân văn nên nhân dịp giveaway này, Chủ kênh đã lập quỹ giấu tên để mọi người có thể cùng giúp đỡ và tạo điều kiện cho những người có hoàn cảnh khó khăn. Chủ kênh định nghĩa một cặp subscribers là cặp "may mắn" nếu tổng giá trị hai mã số của cặp này lớn hơn tổng giá trị hai hộp quà mà cặp này đang sở hữu. Nói cách khác, cặp (i, j) (1 ≤ i, j ≤ n) là cặp "may mắn" nếu ai + aj > bi + bj. Với mỗi cặp "may mắn" mà chủ kênh tìm được, chủ kênh sẽ quyên góp 1 USD vào quỹ từ thiện giấu tên.

Hãy giúp chủ kênh tính số tiền mà anh ấy sẽ quyên góp vào quỹ từ thiện của mình.

Input:

• 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 a1, a2,..., an (1 ≤ ai ≤ 10, 1 ≤ i ≤n);

• Dòng thứ ba chứa n số nguyên b1, b2,..., bn (1 ≤ bi ≤10°, 1 ≤i ≤n).

Output: In ra kết quả là số tiền (đơn vị USD) mà chủ kênh sẽ quyên góp vào quỹ giấu tên trong sự kiện giveaway này.

Input:

4
3 2 4 5
2 3 6 4

Output:

1

Giải thích: Cặp (1,4) là cặp subscribers "may mắn".

Input:

4
3 2 4 5
2 2 6 4

Output:

3

Giải thích: Các cặp (1,2), (1, 4), (2, 4) là các cặp subscribers "may mắn".