HSG12 Hà Nội 2025 - Tin học Bảng A (trích 4 trang) — đề thi, lời giải và phòng thi thử

HSG12 Hà Nội 2025 - Tin học Bảng A (trích 4 trang)

Nguồn: Previously reviewed PDF copied without content changes

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

Câu 1. Trí tuệ nhân tạo

Một trí tuệ nhân tạo cần kết nối với một máy chủ từ xa để đồng bộ dữ liệu. Máy chủ này hoạt động theo một chu kỳ cố định để bảo trì và tối ưu hiệu năng:

$X$ giây ở trạng thái "Online" (cho phép kết nối);

Sau đó, $S$ giây ở trạng thái "Offline" (từ chối mọi kết nối).

Chu kỳ này lặp lại liên tục và bắt đầu từ giây thứ 1 với trạng thái "Online".

Yêu cầu: Một trí tuệ nhân tạo gửi yêu cầu kết nối đến máy chủ vào giây thứ $T$ . Hãy kiểm tra tại giây thứ $T$ , máy chủ đang ở trạng thái "Online" hay "Offline"?

Dữ liệu vào từ tệp TTNT.INP

Dòng đầu tiên gồm số nguyên dương $X$ ( $1 \leq X \leq 109$ );

Dòng thứ hai gồm số nguyên dương $S$ ( $1 \leq S \leq 109$ );

Dòng thứ ba gồm số nguyên dương $T$ ( $1 \leq T \leq 109$ ).

Kết quả ghi ra tệp TTNT.OUT

Nếu tại giây thứ $T$ máy chủ đang "Offline" ghi ra số 0, máy chủ đang "Online" ghi ra số 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.

Câu 2. Đèn lồng

Nhân dịp Tết Trung thu, khu phố đã treo $N$ chiếc đèn lồng có màu vàng và màu đỏ, từ trái sang phải. Một dãy đèn lồng liên tiếp được gọi là "đẹp" nếu số lượng đèn màu vàng gấp đôi số lượng đèn màu đỏ.

Yêu cầu: Cho một xâu $S$ chỉ gồm các ký tự 'V' và 'D' mô tả dãy đèn lồng, ký tự 'V' mô tả đèn lồng màu vàng và ký tự 'D' mô tả đèn lồng màu đỏ. Hãy tìm độ dài của dãy đèn lồng "đẹp" dài nhất.

Dữ liệu vào từ tệp DL.INP

Một xâu $S$ chỉ gồm các ký tự 'V' và 'D' mô tả dãy đèn có độ dài không vượt quá $105$ .

Kết quả ghi ra tệp DL.OUT

Một số nguyên duy nhất là kết quả của bài toá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. Rừng cây

Trong một khu rừng có $N$ cây. Các cây được đánh số từ 1 đến $N$ , có tất cả $M$ loại cây. Cây thứ $i$ thuộc loại $B i$ ( $1 \leq B i \leq M$ ) và có chiều cao là $C i$ .

Chênh lệch chiều cao của rừng cây được tính theo công thức: tổng các giá trị tuyệt đối của hiệu chiều cao giữa tất cả các cặp cây khác loại nhau. Nghĩa là chênh lệch chiều cao của rừng cây được tính bằng công thức: $\sum |C i - C j | \forall 1 \leq i < j \leq N và B i \neq B j$ .

Yêu cầu: Hãy tính chênh lệch chiều cao của rừng cây đã cho.

Dữ liệu vào từ tệp RC.INP

Dòng đầu tiên gồm hai số nguyên dương $N$ và $M$ ( $1 \leq N \leq 105$ ; $M \leq N$ );

Dòng thứ hai gồm $N$ số nguyên dương $B i$ ( $1 \leq B i \leq M$ );

Dòng thứ ba gồm $N$ số nguyên dương $C i$ ( $1 \leq C i \leq 109$ ).

Kết quả ghi ra tệp RC.OUT

Một số nguyên duy nhất là chênh lệch chiều cao của rừng cây đã cho.

---

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. Dãy F-Fibonacci

Với hai số nguyên dương $X, Y$ cho trước, dãy F-Fibonacci là dãy số được định nghĩa như sau:

$F 0 = X; F 1 = Y$ ;

$F i = F i-1 + F i-2$ với mọi $i \geq 2$ .

Cho dãy $A$ gồm $N$ số nguyên dương $A 1, A 2, \dots, A N$ . Người ta muốn chia dãy $A$ thành các đoạn con liên tiếp sao cho tổng các phần tử của mỗi đoạn con đều thuộc dãy F-Fibonacci.

Yêu cầu: Hãy đếm số cách chia dãy $A$ thành các đoạn con sao cho tổng các phần tử của mỗi đoạn con đều thuộc dãy F-Fibonacci.

Dữ liệu vào từ tệp DF.INP

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

Dòng thứ hai gồm $N$ số nguyên dương $A 1, A 2, \dots, A N$ ( $1 \leq A i \leq 109$ ; $1 \leq i \leq N$ );

Dòng thứ ba gồm hai số nguyên dương $X, Y$ ( $1 \leq X \leq Y \leq 100$ ).

Kết quả ghi ra tệp DF.OUT

Một số nguyên duy nhất là kết quả bài toán sau khi chia dư cho $109 + 7$ .

---

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. Thông tin

Trong sứ mệnh khám phá bản đồ, một rô-bốt tự hành được giao một nhiệm vụ di chuyển dọc theo một dãy gồm $N$ điểm thu thập thông tin, được đánh số từ 1 đến $N$ . Điểm thu thập thông tin $i$ ( $1 \leq i \leq N$ ) có lượng dữ liệu là $A i$ , nếu rô-bốt thu thập thông tin tại điểm này thì sẽ tiêu thụ $W i$ năng lượng.

Rô-bốt được lập trình để thu thập các điểm thông tin liên tiếp và phải tuân thủ nghiêm ngặt các điều kiện sau:

Số lượng điểm thu thập thông tin được quét phải là bội số của $K$ (để đảm bảo tính toàn vẹn của các gói thông tin);

Tổng năng lượng tiêu thụ để rô-bốt thu thập thông tin không được vượt quá giới hạn $S$ của pin. Coi năng lượng tiêu thụ khi di chuyển qua các điểm thông tin bằng 0.

Yêu cầu: Hãy viết chương trình cho rô-bốt để tìm ra các điểm thông tin liên tiếp thỏa mãn điều kiện trên mà tổng lượng dữ liệu thu thập được là lớn nhất.

Dữ liệu vào từ tệp TT.INP

Dòng đầu tiên gồm ba số nguyên $N, K, S$ ( $1 \leq K \leq N \leq 105$ ; $1 \leq S \leq 1012$ );

Dòng thứ hai gồm $N$ số nguyên $A 1, A 2, \dots, A N$ ( $|A i | \leq 109$ ; $1 \leq i \leq N$ );

Dòng thứ ba gồm $N$ số nguyên $W 1, W 2, \dots, W N$ ( $0 \leq W i \leq 109$ ; $1 \leq i \leq N$ ).

Kết quả ghi ra tệp TT.OUT

Gồm một số nguyên là lượng dữ liệu thu thập được lớn nhất. Nếu không tồn tại các điểm thông tin liên tiếp khả thi, ghi ra số 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 độ