Đề thi thử Chuyên Sư Phạm - 2026

Sau bài kiểm tra online, giáo sư X muốn xếp thứ hạng cho \(n\) học trò của mình dựa trên bài làm của chúng. Với mỗi bạn tham gia kì thi này, máy tính ghi lại hai thông tin: số bài đã làm được và tổng số thời gian làm bài. Để cho tiện ta gọi \(p_i, t_i\) tương ứng là số bài đã nộp và tổng thời gian làm bài của học sinh thứ \(i\).

Học sinh \(i\) được xếp hạng cao hơn học sinh \(j\) nếu:

• Học sinh \(i\) giải được nhiều bài hơn \(j\) (\(p_i > p_j\)).
• Hoặc giải được cùng số bài nhưng tổng thời gian lại ít hơn \(j\) (\(p_i = p_j\) và \(t_i < t_j\)).

Với những bạn giải được cùng số bài trong cùng một khoảng thời gian bằng nhau thì coi là cùng thứ hạng.

Yêu cầu: Nếu xếp các bạn theo thứ hạng giảm dần, hãy cho biết xem có bao nhiêu thí sinh có cùng hạng với bạn đứng ở vị trí thứ \(k\) trong danh sách đã sắp xếp đó?

Input

• Dòng đầu gồm hai số nguyên dương \(n, k\) (\(n, k \le 10^5\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) ghi hai số nguyên \(p_i, t_i\) (\(p_i, t_i \ge 0\)).

Output

• Ghi ra một số nguyên duy nhất là số người có cùng thứ hạng với bạn ở vị trí thứ \(k\) sau khi đã sắp xếp.

Example

7 2
4 10
4 10
4 10
3 20
2 1
2 1
1 10

3

5 4
3 1
3 1
5 3
3 1
3 1

4

Constraints

• \(n, k \le 10^5\).
• Các giá trị \(p_i, t_i\) nằm trong giới hạn kiểu số nguyên 32-bit.

Giáo sư X đang cần tiền đầu tư cho một dự án lớn. Số tiền cần có là \(n\) đồng nhưng tài khoản của ông đang có \(0\) đồng. Ông bèn đến ngân hàng và khóc… Bụt hiện lên dưới chức danh giám đốc ngân hàng hỏi “Vì sao con khóc?”.

Sau khi nghe kể sự tình, Bụt bảo: “Được rồi, bây giờ mỗi ngày con có thể kiếm tiền nạp thêm vào tài khoản một số tiền tùy ý (có thể \(0\) đồng), rồi cuối ngày ta sẽ hô biến để số tiền trong tài khoản của con tăng lên gấp đôi. Tuy nhiên nếu có thời điểm tài khoản của con có nhiều hơn \(n\) đồng ta sẽ thu lại hết và tài khoản của con trở lại thành \(0\) đồng”.

Giáo sư X chỉ có \(k\) ngày để huy động tiền, hãy cho biết số tiền ít nhất giáo sư X cần kiếm thêm để trong thời hạn đến hết ngày thứ \(k\), có thời điểm số tiền trong tài khoản của giáo sư X đúng bằng \(n\). Khi đó giáo sư X chỉ cần cảm ơn ông Bụt và rút hết \(n\) đồng ra đầu tư.

Input

• Dòng đầu tiên chứa số nguyên dương \(T \le 10^5\) là số lượng bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(n, k \le 10^{18}\) cách nhau bởi dấu cách ứng với một bộ test.

Output

• Ghi ra thiết bị xuất chuẩn ứng với mỗi bộ test, ghi ra một số nguyên duy nhất trên một dòng là số tiền giáo sư X phải tự kiếm thêm để nạp vào tài khoản của mình.

Example

4
10 2
99 5
123456789 9
999999999 100

3
8
482256
21

Giáo sư X vừa chế tạo ra các con robot có thể leo cầu thang. Để thử nghiệm, ông cho dựng một cầu thang với \(n\) bậc. Bậc thứ \(i\) cao hơn bậc liền trước đó \(a_i\) cm. Cụ thể, coi mặt đất có độ cao là \(0\), bậc đầu tiên cao hơn mặt đất \(a_1\) cm, bậc thứ \(2\) cao hơn bậc thứ nhất \(a_2\) cm, ...

Ông có \(q\) con robot, chân của mỗi con lần lượt có chiều cao là \(k_1, k_2, \dots, k_q\). Biết rằng, một con robot chỉ leo được các bậc cầu thang có độ chênh lệch độ cao so với bậc trước đó nhỏ hơn hoặc bằng chiều cao của chân nó.

Yêu cầu: Hãy xác định độ cao tối đa so với mặt đất của mỗi con robot khi nó leo các bậc cầu thang của Giáo sư X.

Input

• Dòng đầu tiên là số \(t\) – số lượng test (\(1 \le t \le 100\)).
• Tiếp theo là \(t\) bộ test, mỗi bộ test gồm:
  • Dòng đầu tiên chứa hai số nguyên \(n, q\) (\(1 \le n, q \le 2 \cdot 10^5\)).
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).
  • Dòng thứ ba chứa \(q\) số nguyên \(k_1, k_2, \dots, k_q\) (\(0 \le k_i \le 10^9\)).
• Dữ liệu đảm bảo rằng tổng của các số \(n\) trong các test không vượt quá \(2 \cdot 10^5\), và tổng của các số \(q\) không vượt quá \(2 \cdot 10^5\).

Output

• Ứng với mỗi test, hãy ghi ra một dòng gồm \(q\) số nguyên tương ứng với độ cao tối đa của từng con robot.

Example

3
4 5
1 2 1 4
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000

1 4 8 8 8 
0 2 
3000000000 

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n, q \le 5000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Bản đồ nền một khu dự án nhà ở là một hình chữ nhật kích thước \(m \times n\) được chia thành lưới ô vuông đơn vị. Các hàng của lưới được đánh số từ \(1\) tới \(m\) từ trên xuống dưới và các cột của lưới được đánh số từ \(1\) tới \(n\) từ trái qua phải. Ô nằm trên giao của hàng \(i\) và cột \(j\) được gọi là ô \((i, j)\). Trong bản thiết kế, trên mỗi ô \((i, j)\) của lưới, người ta muốn xây một tòa nhà hình trụ có chiều cao \(h_{ij}\) và đáy chiếm toàn bộ ô đó.

Từ nóc một tòa nhà, nhìn theo \(4\) hướng song song với cạnh hình chữ nhật nền, nếu hướng nào cũng bị một tòa nhà khác cao hơn chắn tầm mắt thì tòa nhà đó bị coi là không hợp phong thủy và rất khó bán các căn hộ. Ban quản lý dự án muốn nhờ bạn xác định số lượng những tòa nhà không hợp phong thủy trong thiết kế của dự án.

Input

• Dòng \(1\) chứa hai số nguyên dương \(m, n \leq 1000\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên dương, số thứ \(j\) là \(h_{ij} \leq 10^6\).
• Các số trên một dòng được ghi cách nhau ít nhất một dấu cách.

Output

• Ghi ra một số nguyên duy nhất là số lượng những tòa nhà không hợp phong thủy trong thiết kế của dự án.

Example

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

2

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(m, n \leq 100\).
• Subtask \(2\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Bạn có \(n\) viên gạch, viên gạch thứ \(i\) có trọng lượng là \(w_i\) và độ chịu lực là \(s_i\). Bạn cần xây một tháp bằng cách chồng các viên gạch lên nhau sao cho độ chịu lực của mỗi viên gạch phải lớn hơn hoặc bằng tổng trọng lượng của các viên gạch phía trên nó.

Yêu cầu: Hãy tìm cách xây một tháp bằng nhiều viên gạch nhất.

Input

• Dòng 1 chứa số nguyên dương \(n \le 10^5\).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(w_i, s_i \le 10^9\) cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là số viên gạch tối đa có thể dùng để xếp tháp.

Example

6
10 20
20 10
1 5
50 100
100 1
2 200

4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 2000\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.