Duyên hải Bắc Bộ 2026 - Khối 10

Duyên hải Bắc Bộ 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. Dãy số

Alice tạo dãy số nguyên a₁, a₂, ⋯, a_N, cô cần thống kê số bộ ba chỉ số (i, j, k) thỏa mãn hai điều kiện sau:

• 1 ≤ i < j < k ≤ N.

• a_i ≤ a_j ≥ a_k hoặc a_i ≥ a_j ≤ a_k.

Yêu cầu: Cho dãy gồm N số nguyên a₁, a₂, ⋯, a_N, hãy đếm số lượng bộ ba thỏa mãn.

Input

• Dòng đầu chứa số nguyên dương N (N ≤ 3 × 10⁵).

• Dòng thứ hai chứa N số nguyên a₁, a₂, ⋯, a_N (|a_i| ≤ 10⁹).

Output

Một số nguyên là số lượng bộ ba thỏa mãn.

Scoring

Sample Input 1

3
1 2 3

Sample Output 1

0

Sample Input 2

4
1 3 2 4

Sample Output 2

2

Sample Input 3

4
1 1 1 1

Sample Output 3

4

---

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. Đường đi

Alice mới tạo ra một trò chơi tìm đường đi trên mặt phẳng tọa độ. Cụ thể, một nhân vật xuất phát tại vị trí (x_s, y_s) cần di chuyển tới vị trí (x_t, y_t) trong thời gian ngắn nhất. Tại mỗi đơn vị thời gian, giả sử nhân vật đang ở vị trí (x₁, y₁) thì có thể di chuyển tới vị trí (x₂, y₂) nếu max(|x₁ - x₂|, |y₁ - y₂|) = 1. Để trò chơi thêm thú vị, Alice đặt K vật phẩm ở K vị trí (u₁, v₁), (u₂, v₂), ⋯, (u_K, v_K), ngoài việc di chuyển với thời gian ngắn nhất, người chơi cần chọn đường đi để thu thập được nhiều vật phẩm nhất. Nhân vật di chuyển tới vị trí có vật phẩm sẽ thu thập được vật phẩm ở vị trí đó và thời gian thu thập là không đáng kể.

Yêu cầu: Cho các thông tin (x_s, y_s), (x_t, y_t) và (u₁, v₁), (u₂, v₂), ⋯, (u_K, v_K), hãy tìm đường đi từ vị trí (x_s, y_s) đến (x_t, y_t) với thời gian ngắn nhất, trong số các đường đi ngắn nhất đó, chọn con đường đi qua nhiều vị trí chứa vật phẩm nhất.

Input

• Dòng đầu chứa năm số nguyên x_s, y_s, x_t, y_t, K (|x_s|, |y_s|, |x_t|, |y_t| ≤ 10⁹; K ≤ 10⁵);

• Dòng thứ i trong K dòng sau chứa hai số nguyên u_i, v_i (|u_i|, |v_i| ≤ 10⁹).

Output

Gồm một số nguyên không âm là số vật phẩm nhiều nhất có thể thu thập được.

Scoring

Sample Input 1

0 0 4 0 3
1 1
3 -1
2 0

Sample Output 1

3

Sample Input 2

0 0 4 0 4
1 1
2 2
2 0
3 -1

Sample Output 2

3

Sample Input 3

0 0 2 2 1
0 1

Sample Output 3

0

Notes

• Ví dụ 1: (0, 0) → (1, 1) → (2, 0) → (3, -1) → (4, 0)

• Ví dụ 2: (0, 0) → (1, 1) → (2, 0) → (3, -1) → (4, 0)

• Ví dụ 3: (0, 0) → (1, 1) → (2, 2)

---

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. Đổ nước

Alice có N bình nước giống nhau, mỗi bình có thể chứa được V lít nước. Hiện tại, bình thứ i (1 ≤ i ≤ N) chứa v_i lít nước (v₁ + v₂ + ⋯ + v_N = V). Alice muốn thực hiện một dãy các lần đổ nước giữa các bình để số lượng bình rỗng là nhiều nhất. Mỗi lần cô có thể đổ nước từ bình i sang bình j nếu v_i ≥ v_j một lượng nước bằng v_j lít, sau khi đổ bình i còn v_i - v_j lít, bình j có 2v_j lít.

Yêu cầu: Hãy tìm một dãy các lần đổ nước để số bình rỗng là nhiều nhất.

Input

Dòng đầu chứa số nguyên T (T ≤ 10) là số bộ dữ liệu, tiếp theo là các nhóm dòng, mỗi nhóm có khuôn dạng:

• Dòng đầu của nhóm chứa số nguyên dương N (2 ≤ N ≤ 10).

• Dòng thứ hai của nhóm chứa N số nguyên dương v₁, v₂, ⋯, v_N (v₁ + v₂ + ⋯ + v_N = V ≤ 10¹²).

Output

Gồm T nhóm dòng, mỗi nhóm mô tả lời giải tương ứng một bộ dữ liệu theo khuôn dạng:

• Dòng đầu ghi số nguyên S là số lần đổ nước;

• Dòng thứ t (1 ≤ t ≤ S) trong S dòng sau, mỗi dòng ghi hai số i, j cho biết lần đổ thứ t đổ nước từ bình i sang bình j.

Scoring

Sample Input 1

2
3
1 2 3
4
1 1 1 1

Sample Output 1

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

Notes

• Với bộ dữ liệu thứ nhất có thể nhận được 1 bình rỗng. (1, 2, 3) → (2, 2, 2) → (2, 0, 4)

• Với bộ dữ liệu thứ hai có thể nhận được 3 bình rỗng. (1, 1, 1, 1) → (2, 0, 2, 0) → (4, 0, 0, 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.