Olympic 30/4 2026 - Khối 10 — đề thi, lời giải và phòng thi thử

Olympic 30/4 2026 - Khối 10

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Thí nghiệm

Phong là một học sinh rất say mê các hoạt động STEM và rất thích thực hiện những thí nghiệm thực tế. Trong một lần thí nghiệm, Phong đã đo nhiệt độ trung bình trong $N$ ngày liên tiếp và được các kết quả là các số thực đôi một khác nhau. Phong chuyển các kết quả này thành một dãy gồm các số nguyên từ $1$ đến $N$ , mỗi số xuất hiện đúng một lần. Số ở ngày thứ $i$ là $A i$ , cho biết rằng trong $N$ ngày mà Phong thực hiện thí nghiệm có đúng $A i -1$ ngày mà nhiệt độ đo được thấp hơn nhiệt độ ở ngày thứ $i$ .

Tiếp theo, Phong thực hiện các bước tách nhóm dữ liệu. Với mỗi bước, Phong sẽ tìm ngày có nhiệt độ cao nhất và ngày có nhiệt độ thấp nhất trong dãy, sau đó tách dữ liệu nhiệt độ của các ngày nằm trong đoạn giữa hai ngày này (kể cả hai ngày có nhiệt độ cao nhất và thấp nhất) thành một nhóm, và nối dữ liệu của các ngày còn lại thành một dãy mới (giữ nguyên thứ tự). Phong lặp lại quy trình này trên dãy mới cho đến khi dãy này trở thành dãy rỗng và đếm số nhóm đã tách được.

Yêu cầu : Vì dữ liệu gồm rất nhiều ngày nên việc tính toán bằng tay có thể mất rất nhiều thời gian, Phong muốn viết một chương trình tính nhanh số nhóm mà Phong tách được. Hãy giúp Phong tính toán thông tin này.

Input

Dòng đầu tiên gồm một số nguyên dương $N$ $(1 \leq N \leq 2 \times 105)$ .

Dòng tiếp theo gồm $N$ số nguyên dương $A 1, A 2, \dots, A N$ $(1 \leq A i \leq N)$ .

Output

Một số duy nhất là số nhóm mà Phong tách được.

Scoring

Subtask	Điểm	Ràng buộc
1	$2$	$N \leq 2000$
2	$2{,}5$	Sau mỗi thao tác tách nhóm, ngày đầu tiên trong dãy mới luôn là ngày có nhiệt độ thấp nhất
3	$2{,}5$	Không có giới hạn gì thêm

Sample Input 1

6
3 5 1 4 6 2

Sample Output 1

Sample Input 2

7
1 6 2 7 3 4 5

Sample Output 2

Notes

Ví dụ thứ nhất:

Trong thao tác tách nhóm đầu tiên, ngày có nhiệt độ cao nhất là ngày thứ $5$ , thấp nhất là ngày thứ $3$ . Phong tách được nhóm $[1,4,6]$ và dãy còn lại là $[3,5,2]$ .

Trong thao tác tiếp theo, Phong tách được nhóm $[5,2]$ và dãy còn lại là $[3]$ .

Trong thao tác cuối cùng, Phong tách được nhóm $[3]$ và dãy còn lại là dãy rỗng.

Ví dụ thứ hai:

Thao tác đầu tiên, Phong tách được nhóm $[1,6,2,7]$ . Dãy còn lại là $[3,4,5]$ .

Thao tác thứ hai, Phong tách được nhóm $[3,4,5]$ . Dãy còn lại là dãy rỗng.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Trò chơi

Trong buổi lễ khai mạc của kỳ thi Olympic truyền thống 30 tháng 4, bạn Lê được Ban tổ chức mời tham gia một trò chơi nhỏ. Quản trò viết lên bảng $N$ số nguyên $A 1, A 2, \dots, A N$ thành một vòng tròn và bí mật chọn ra một đoạn liên tiếp gồm không quá $N-1$ số trên vòng tròn đó. Sau đó, quản trò nói cho Lê biết rằng tổng các số trong đoạn được chọn là một số không nhỏ hơn $L$ và không lớn hơn $R$ . Lê được phép chọn một vị trí bất kỳ trên bảng, và nếu vị trí đó nằm trong đoạn mà quản trò đã chọn thì Lê sẽ nhận được một phần quà. Lê muốn khả năng nhận quà của mình là lớn nhất có thể nên muốn tính toán xem với mỗi vị trí $i$ trên vòng tròn, có bao nhiêu đoạn đi qua vị trí này mà quản trò có thể chọn.

Yêu cầu : Hãy giúp Lê giải quyết bài toán trên.

Input

Dòng đầu tiên gồm ba số nguyên $N, L, R$ $(2 \leq N \leq 2 \cdot 105; -2 \cdot 1014 \leq L \leq R \leq 2 \cdot 1014)$ .

Dòng tiếp theo gồm $N$ số nguyên $A 1, A 2, \dots, A N$ $(-10 9 \leq A i \leq 109)$ .

Output

Một dòng duy nhất gồm $N$ số nguyên không âm, số nguyên thứ $i$ là số lượng đoạn đi qua vị trí $i$ mà quản trò có thể chọn.

Scoring

Subtask	Điểm	Ràng buộc
1	$30%$	$N \leq 200$
2	$30%$	$N \leq 5000$
3	$20%$	$A i \geq 0$ với mọi $i = 1, 2, \dots, N$
4	$20%$	Không có ràng buộc nào thêm

Sample Input 1

5 6 7
1 2 3 4 5

Sample Output 1

2 1 2 1 1

Sample Input 2

3 1 2
1 -1 2

Sample Output 2

1 1 2

Notes

Trong ví dụ thứ nhất, ác đoạn thỏa mãn là $(1, 2, 3)$ , $(3, 4)$ , $(5, 1)$ . Trong các đoạn này, vị trí $1$ , $3$ và $5$ có $2$ lần xuất hiện, các vị trí khác có $1$ lần xuất hiện.

Trong ví dụ thứ hai, đoạn thỏa mãn là $(1)$ , $(-1, 2)$ , $(2)$ . Trong các đoạn này, vị trí $1$ và $2$ xuất hiện $1$ lần, vị trí $3$ xuất hiện $2$ lần.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Thoát hiểm

Khách sạn nơi các thí sinh tham dự kỳ thi Olympic truyền thống 30 tháng 4 đang lưu trú có $N$ phòng được đánh số từ $1$ đến $N$ , được nối với nhau bằng $M$ hành lang hai chiều. Hành lang thứ $i$ nối hai phòng $U i$ và $V i$ , có độ dài $L i$ . Hệ thống các hành lang ở khách sạn đảm bảo tính liên thông giữa các phòng, nghĩa là giữa hai phòng bất kỳ luôn tồn tại đường đi trực tiếp hoặc qua các phòng trung gian.

Sau khi hoàn thành các bài thi, có $Q$ thí sinh được ban tổ chức kỳ thi mời tham gia một trò chơi. Ban tổ chức chuẩn bị còi cảnh báo ở $K$ phòng được đánh số $X 1, X 2, \dots, X K$ . Thí sinh thứ $i$ sẽ được đưa đến phòng đánh số $S i$ và cần phải di chuyển đến phòng được đánh số $T i$ và các thí sinh cần tránh xa các phòng có còi cảnh báo nhất có thể.

Độ an toàn của một phòng được tính bằng khoảng cách ngắn nhất tính theo tổng độ dài các hành lang nối từ phòng đó đến một phòng có báo động. Độ an toàn của một đường đi là giá trị nhỏ nhất của độ an toàn của các phòng trên đường đi đó (kể cả phòng xuất phát và phòng đích đến). Mỗi thí sinh cần chọn đường đi có độ an toàn cao nhất để di chuyển đến đích. Những thí sinh chọn được một lộ trình tối ưu sẽ nhận được một phần quà từ ban tổ chức kỳ thi.

Yêu cầu : Hãy giúp ban tổ chức tính giá trị độ an toàn lớn nhất có thể đạt được cho mỗi thí sinh để có thể trao quà cho các thí sinh chọn được lộ trình tối ưu.

Input

Dòng đầu chứa hai số nguyên $N, M$ $(1 \leq N \leq 105; 1 \leq M \leq 2 \cdot 105)$ ;

Mỗi dòng trong số $M$ dòng tiếp theo gồm ba số nguyên $U i, V i, L i$ $(1 \leq U i, V i \leq N; 1 \leq L i \leq 106)$ ;

Dòng tiếp theo chứa một số nguyên $K$ $(1 \leq K \leq N)$ ;

Dòng tiếp theo chứa $K$ số nguyên $X 1, X 2, \dots, X K$ $(1 \leq X i \leq N)$ ;

Dòng tiếp theo chứa một số nguyên $Q$ $(1 \leq Q \leq 105)$ ;

Dòng thứ $i$ trong số $Q$ dòng tiếp theo gồm hai số nguyên $S i, T i$ $(1 \leq S i, T i \leq N)$ .

Output

In ra $Q$ dòng, mỗi dòng một số nguyên là độ an toàn lớn nhất có thể đạt được cho thí sinh tương ứng.

Scoring

Subtask	Điểm	Ràng buộc
1	1	$K \leq 10; Q = 1; M = N - 1$ và mỗi phòng kết nối với không quá $2$ hành lang
2	1	$K \leq 10; Q = 1; M = N - 1$
3	1	$M = N - 1$ và mỗi phòng kết nối với không quá $2$ hành lang
4	1	$M = N - 1$
5	1	$Q = 1$
6	1	Không có ràng buộc gì thêm

Sample Input 1

Sample Output 1

4
0

Notes

Sơ đồ của khách sạn có dạng như hình dưới. Độ an toàn của các phòng trong trường hợp này lần lượt là $3, 0, 7, 7, 4$ .

Thí sinh đầu tiên có thể di chuyển theo lộ trình $3 \to 4 \to 5$ có độ an toàn của các phòng lần lượt là $7, 7, 4$ và độ an toàn thấp nhất là $4$ . Nếu thí sinh di chuyển theo lộ trình $3 \to 1 \to 5$ thì độ an toàn thấp nhất sẽ là $3$ và không phải lộ trình tối ưu.

Thí sinh thứ hai có lộ trình di chuyển kết thúc ở một phòng có còi báo động nên độ an toàn thấp nhất là $0$ .

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Cấu trúc đề và tiến độ