TLEoj Contest #01 - Những bông hoa
Xem PDFKhu vườn của T có n tảng đá xếp thành một hàng dọc. Một hôm, T nhìn ra vườn và nhận thấy rằng trên một số tảng đá đã mọc ra những bông hoa. Cảm thấy không thoải mái với điều này, T quyết định chọn một nhóm dài nhất các tảng đá nằm kề nhau, và ra vườn nhổ hết các bông hoa trên những tảng đá. T là một người rất lười biếng, nên anh ta muốn công việc của mình phải thật hiệu quả: trong số các tảng đá được chọn, số tảng đá có hoa phải chiếm một tỉ lệ ít nhất là \frac{u}{v}. Đồng thời, T cũng muốn dọn dẹp càng nhiều tảng đá càng tốt (chuỗi các tảng đá được chọn phải càng dài càng tốt). Các bạn hãy cho biết chuỗi các tảng đá dài nhất mà T có thể chọn bao gồm bao nhiêu tảng đá.
Input, Output và Subtasks
Input: (bàn phím)
- Dòng đầu tiên gồm các số nguyên dương n, u, v (n \le 10^5; u \le v \le 10^9)
- Dòng thứ hai gồm một xâu S gồm n kí tự tượng trưng cho trạng thái có/không có hoa của các viên đá. Kí tự thứ i là
.nếu viên đá thứ i không có hoa và là#nếu viên đá thứ i có hoa. - Dữ liệu đầu vào đảm bảo có ít nhất một viên đá có hoa.
Output: (màn hình)
- In ra một số nguyên duy nhất là độ dài chuỗi đá dài nhất tìm được.
Subtasks
- Subtask 1 (25\%): n \le 100
- Subtask 2 (25\%): n \le 1000
- Subtask 3 (25\%): u = v = 1
- Subtask 4 (25\%): Không có giới hạn gì thêm
Sample 1
Input (bàn phím)
11 12 20
...##.##...
Output (màn hình)
6
Notes
Ta có thể chọn chuỗi đá từ vị trí thứ 3 đến vị trí thứ 8 hoặc từ vị trí thứ 4 đến vị trí thứ 9. Các chuỗi đá này có tỉ lệ số tảng đá có hoa là \frac{4}{6} \ge \frac{12}{20}.
Sample 2
Input (bàn phím)
11 16 20
...##.##...
Output (màn hình)
5
Notes
Ta có thể chọn chuỗi đá từ vị trí thứ 4 đến vị trí thứ 8. Chuỗi đá này có tỉ lệ số tảng đá có hoa là \frac{4}{5} \ge \frac{16}{20}.
Sample 3
Input (bàn phím)
11 1 1
...#####...
Output (màn hình)
5
Notes
Ta có thể chọn chuỗi đá từ vị trí thứ 4 đến vị trí thứ 8 gồm toàn những tảng đá có hoa.
Bình luận