Chọn ĐTQG Quảng Ngãi 2025

Chọn ĐTQG Quảng Ngãi 2025

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. Số đặc biệt

---

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. Thu hoạch

---

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. Thuê nhân viê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 4. QNROAD

Giám đốc công ty XYZ xây dựng kế hoạch thuê nhân công để làm dự án đường cao tốc kết nối Đông Tây của tỉnh Quảng Ngãi. Dự án cần triển khai trong n tháng được đánh số từ 1 đến n. Biết rằng bắt đầu vào một tháng, dự án có quyền thuê thêm nhân công. Để thuê mỗi nhân công cần một khoản chi phí trả cho nhà tuyển dụng là H. Mỗi tháng, mỗi nhân công được thuê sẽ được trả một khoản lương S kể cả không làm việc. Kết thúc mỗi tháng, dự án có quyền sa thải nhân công hoặc không. Để sa thải mỗi nhân công cần trả một khoản chi phí D.

Trước khi dự án bắt đầu thì chưa có nhân công nào. Tháng thứ i của dự án cần tối thiểu a_i nhân công. Kết thúc tháng thứ n, toàn bộ nhân công bị sa thải.

Yêu cầu: Hãy giúp Giám đốc xây dựng kế hoạch thuê nhân công để dự án hoàn thành với chi phí thuê nhân công ít nhất có thể.

Input

Dòng thứ nhất chứa số nguyên n (1 ≤ n ≤ 4 × 10⁵).

Dòng thứ hai chứa ba số nguyên H, S, D (H, S, D ≤ 10⁶).

Dòng thứ ba chứa n số nguyên dương a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶).

Output

Một số nguyên là chi phí tối thiểu tìm được.

Subtasks

Subtask 1 (40 % số điểm): n ≤ 10³.

Subtask 2 (30 % số điểm): n ≤ 10⁵.

Subtask 3 (30 % số điểm): Không có ràng buộc nào thêm.

Sample Input

4
7 8 9
22 24 29 34

Sample Output

1416

---

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 5. ROBOT

Trên sân hình vuông có n × n ô vuông, các dòng và cột được đánh số từ 1 đến n. Tại mỗi ô (i, j) hoặc chứa chướng ngại vật hoặc ghi số nguyên a_{i, j} (1 ≤ i, j ≤ n, -1 ≤ a_{i, j} ≤ 10⁶). Nếu a_{i, j} = -1 thì ô đó là chướng ngại vật. Robot nhận nhiệm vụ di chuyển từ ô (1, 1) đến ô (n, n). Tại ô (i, j) robot chỉ được di chuyển sang ô (i, j + 1) hoặc (i + 1, j), không được di chuyển ra khỏi sân, không được di chuyển vào ô có chướng ngại vật. Nếu đến được đích thì điểm thưởng sẽ được tính bằng tích của tất cả các số ghi trên các ô mà nó đi qua. Để tăng độ khó, người ta yêu cầu điểm thưởng phải là bội của một số nguyên k cho trước.

Yêu cầu: Đếm số đường đi mà robot đi đến được đích sao cho điểm thưởng là bội số của một số nguyên k cho trước, kết quả lấy modulo 998244353.

Input

Output

Số lượng đường đi thỏa mãn yêu cầu sau khi modulo 998244353.

Subtasks

Subtask 1 (40 % số điểm): n ≤ 500, k = 1.

Subtask 2 (15 % số điểm): n ≤ 500, k = 2.

Subtask 3 (15 % số điểm): n ≤ 100, k ≤ 20.

Subtask 4 (30 % số điểm): Không có ràng buộc nào thêm.

Sample Input 1

2 2
3 6
3 2

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3

---

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 6. SPECK

Cho đồ thị n đỉnh được đánh số từ 1 đến n và m cạnh. Cạnh thứ i nối hai đỉnh u_i, v_i. Đồ thị đảm bảo luôn có đường đi giữa hai đỉnh bất kì và giữa hai đỉnh có thể có nhiều cạnh nối giữa chúng.

Đường đi từ a đến b được biểu diễn bằng dãy các đỉnh a = x₁ x₂ ... x_p=b, với 1 ≤ x_i ≤ n, (x_i, x_{i + 1}) là một cạnh của đồ thị. Cạnh (x_i, x_{i + 1}) được gọi là cạnh đặc biệt trên đường đi từ a đến b nếu mọi đường đi từ a đến b phải qua cạnh (x_i, x_{i + 1}).

Yêu cầu: Cho số nguyên k. Tính số lượng cặp đỉnh (a, b) (a < b) sao cho mọi đường đi từ a đến b đi qua ít nhất k cạnh đặc biệt.

Input

Dòng thứ nhất chứa ba số nguyên n, m, k (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵, k ≤ 10⁵).

Dòng thứ i trong m dòng tiếp theo chứa hai số nguyên u_i, v_i (u_i ≠ v_i).

Output

Số lượng cặp đỉnh (a, b) (a < b) sao cho mọi đường đi từ a đến b qua ít nhất k cạnh đặc biệt.

Subtasks

Subtask 1 (70 % số điểm): n ≤ 100.

Subtask 2 (30 % số điểm): Không có ràng buộc nào thêm.

Sample Input

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

Sample Output

1

---

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.