Tuyển sinh lớp 10 chuyên Tin Phổ thông Năng khiếu 2025

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. STREAK

An sử dụng một ứng dụng nhắn tin và muốn biết bạn của mình, Bình, có những khoảng thời gian online liên tục dài nhất là bao lâu trong một ngày. Hệ thống ghi lại trạng thái của Bình mỗi phút trong suốt $T$ phút của một ngày. Trạng thái có thể là một trong ba loại: "ONLINE", "IDLE" (không hoạt động), hoặc "OFFLINE".

Một "chuỗi online" được định nghĩa là một khoảng thời gian liên tục mà trạng thái của Bình là "ONLINE".

Yêu cầu: Cho chuỗi các trạng thái của Bình trong $T$ phút, hãy tìm độ dài của chuỗi online liên tục dài nhất. Nếu Bình không online phút nào, kết quả là 0.

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

Dòng đầu tiên chứa số tự nhiên $T$ ( $1 \leq T \leq 1440$ ), tổng số phút theo dõi trong ngày.

$T$ dòng tiếp theo, mỗi dòng chứa một xâu ký tự là trạng thái của Bình tại phút tương ứng: "ONLINE", "IDLE", hoặc "OFFLINE".

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

Một số nguyên duy nhất là độ dài của chuỗi online liên tục dài nhất.

Sample Input 1

10
ONLINE
ONLINE
IDLE
ONLINE
ONLINE
ONLINE
OFFLINE
ONLINE
ONLINE
IDLE

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.

Câu 2. EVTRIP

Một chiếc xe điện bắt đầu hành trình từ điểm 0 km với pin đầy, dung lượng pin tối đa là $P max$ đơn vị. Mỗi km di chuyển tiêu tốn 1 đơn vị pin.

Trên quãng đường có $N$ trạm sạc. Trạm thứ $i$ (với $i=1, 2, \dots, N$ ) nằm ở vị trí $D i$ km tính từ điểm xuất phát và tại đó xe có thể sạc đầy pin (lên $P max$ ) ngay lập tức.

Xe không thể di chuyển nếu pin không đủ cho 1 km tiếp theo. Đích đến là thành phố ở vị trí $D target$ km.

Yêu cầu: Tìm số lần sạc ít nhất để xe có thể đi từ điểm 0 đến $D target$ . Nếu không thể đến đích, ghi ra -1.

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

Dòng đầu tiên: ba số tự nhiên $N, P max, D target$ ( $0 \leq N \leq 1000, 1 \leq P max \leq 109, 1 \leq D target \leq 109$ ).

$N$ dòng tiếp theo: mỗi dòng chứa một số nguyên $D i$ ( $1 \leq D i < D target$ ).

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

Một số nguyên là số lần sạc ít nhất, hoặc -1 nếu không thể đến đích.

Sample Input 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.

Câu 3. WORDGAME

Một trò chơi xếp chữ trên điện thoại, người chơi có một chuỗi ký tự $s$ . Mỗi lượt chơi được phép xóa một ký tự bất kỳ. Trò chơi kết thúc khi chuỗi còn lại là palindrome (đọc xuôi ngược như nhau). Ví dụ: chuỗi "aca" hoặc "racecar" là chuỗi palindrome.

Yêu cầu: Tìm số lượt chơi ít nhất để chuỗi ban đầu trở thành palindrome.

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

Chuỗi ký tự $s$ ( $1 \leq độ dài \leq 2000$ , chỉ gồm chữ thường).

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

Số lượt chơi ít nhất.

Sample Input 1

abcca

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.

Câu 4. BLOCKOPT

Trong một hệ thống blockchain, thợ đào chọn các giao dịch đang chờ (giả sử có $N$ giao dịch) để đưa vào một khối mới. Mỗi giao dịch thứ $i$ có phí $F i$ và kích thước $S i$ (với $i=1, 2, \dots, N$ ) và $F i, S i$ là các số nguyên dương. Khối có kích thước tối đa là $S max$ ( $S max$ là số nguyên dương). Thợ đào muốn tối đa tổng phí $F i$ sao cho tổng kích thước $S i$ không vượt $S max$ .

Giả sử rằng có $D$ ràng buộc phụ thuộc: nếu giao dịch A được chọn thì giao dịch B cũng phải được chọn. Các phụ thuộc này không tạo thành chu trình.

Yêu cầu: Tìm tổng phí giao dịch lớn nhất.

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

Dòng 1: $N, S max$ ( $1 \leq N \leq 50, 1 \leq S max \leq 1000$ ).

$N$ dòng tiếp theo: $F i, S i$ ( $1 \leq F i, S i \leq 1000$ ) cho giao dịch $i$ .

Dòng tiếp: $D$ ( $0 \leq D \leq N(N-1) 2$ ).

$D$ dòng tiếp (nếu $D>0$ ): $A, B$ (thể hiện cho ràng buộc nếu chọn A phải chọn B, trong đó $A, B \in {1, 2, \dots, N}$ ).

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

Tổng phí lớn nhất.

Sample Input 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: Chưa xác minh thời gian chạy trên toàn miền.

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