Tìm kiếm nhị phân (Ôn tập)

Cho dãy số nguyên \(a\) gồm \(n\) phần tử được sắp xếp tăng dần. Hãy xác định giá trị \(x\) có xuất hiện trong mảng hay không ?

Input

• Dòng đâu tiên chứa số hai số nguyên dương \(n\) và \(k\) - độ dài của dãy, số câu hỏi. \((n, k \leq 100000)\)
• \(n\) số, các phần tử dãy \(a\) \((-10^9 \le a_i \le 10^9)\)
• \(k\) số nguyên dương \(x\) \((-10^9 \le x \le 10^9)\).

Output

• Gồm \(k\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

10 10
1 61 126 217 2876 6127 39162 98126 712687 1000000000
100 6127 1 61 200 -10000 1 217 10000 1000000000 

NO
YES
YES
YES
NO
NO
YES
YES
NO
YES

Cho dãy số nguyên \(a\) gồm \(n\) phần tử được sắp xếp tăng dần. Hãy xác định giá trị lớn nhất của \(i\) sao cho \(a_i \le x\). Nếu không có vị trí thõa mãn in ra \(0\).

Input

• Dòng đâu tiên chứa số hai số nguyên dương \(n\) và \(k\) - độ dài của dãy, số câu hỏi. \((n, k \leq 100000)\)
• \(n\) số, các phần tử dãy \(a\) \((-10^9 \le a_i \le 10^9)\)
• \(k\) số nguyên dương \(x\) \((-10^9 \le x \le 10^9)\).

Output

• Gồm \(k\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

 5 5
 3 3 5 8 9
 2 4 8 1 10

0
2
4
0
5

Cho dãy số nguyên \(a\) gồm \(n\) phần tử được sắp xếp tăng dần. Hãy xác định giá trị nhỏ nhất của \(i\) sao cho \(a_i \ge x\). Nếu không có vị trí thỏa mãn in ra \(n + 1\).

Input

• Dòng đâu tiên chứa số hai số nguyên dương \(n\) và \(k\) - độ dài của dãy, số câu hỏi. \((n, k \leq 100000)\)
• \(n\) số, các phần tử dãy \(a\) \((-10^9 \le a_i \le 10^9)\)
• \(k\) số nguyên dương \(x\) \((-10^9 \le x \le 10^9)\).

Output

• Gồm \(k\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

 5 5
 3 3 5 8 9
 2 4 8 1 10

1
3
4
1
6

Khi nghe tin Đà Nẵng có ca dịch Covid mới, Khôi liền chạy tới tiệm thuốc mua khẩu trang.

Cửa hàng có \(n\) hộp khẩu trang. Giá của mỗi hộp khẩu trang được biểu diễn bằng mảng \(A\). Hộp thứ \(i\) có giá \(A_i\) đồng.

Bất chợt có một người đàn ông tên là Small đến hỏi Khôi vài câu hỏi. Mỗi câu hỏi, Khôi sẽ trả lời số hộp khẩu trang có giá tiền nhỏ hơn \(M\) đồng.

Input

• Dòng đâu tiên chứa số nguyên dương \(N\) \((N \leq 10^5)\).
• Dòng 2 chứa \(N\) số nguyên dương \(A_i\) \((A_i \leq 10^9)\).
• Dòng thứ 3 chứa số nguyên \(Q\) \((Q \leq 10^5)\) - là số câu hỏi.
• \(Q\) dòng tiếp theo, mỗi dòng chứa \(1\) giá tri \(M\) \((M \leq 10^9)\).

Output

• Gồm \(Q\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

5
1 4 10 5 6
4
2
3
5
11

1
1
2
5

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Với mỗi chỉ số \(1 \le i \le N\) đếm xem có bao nhiêu phần tử bé hơn \(a_i\).

Input

• Dòng đầu tiên gồm số nguyên dương \(N\) \((2 \le N \le 10^5)\)
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

• In ra \(N\) số nguyên, số thứ \(i\) cho biết số phần tử nhỏ hơn \(a_i\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3\)
• Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm.

Example

5
3 2 1 1 2 

4 2 0 0 2

Cho \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) rải đều trên một đường tròn theo chiều kim đồng hồ. Hãy tìm cung tròn có độ dài nhỏ nhất mà tổng các số trên cung tròn lớn hơn hoặc bằng \(S\). In ra số lượng số trên cung tròn đó. Nếu không có cung tròn nào thỏa mãn thì in ra \(-1\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, S \ (S \leq 10^{18})\).

• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)

Output

• In ra độ dài cung tròn tìm được

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 2000\)
• Subtask \(3\) (\(40\%\) số điểm): \(n \leq 200000\)

Example

5 7
3 1 1 1 4 

2

5 6
1 1 1 1 4

3

7 80
70 11 32 43 43 11 54

2

Bạn được cho 2 số nguyên dương \(a\) và \(b\).

Viết chương trình tìm số thứ \(n\) chia hết cho \(a\) hoặc \(b\).

Input

• Dòng đâu tiên chứa số nguyên dương \(T\) \((T \leq 10^5)\) - là số câu hỏi.
• \(T\) dòng, mỗi dòng chứa 3 số nguyên dương \(a, b, n\) \((a,b \leq 10^4, N \leq 10^9)\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

1
2 3 10

15