Khu vườn của T có nn 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

2024-11-17 04:55:24

Khu vườn của T có nn 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à uvvu. Đồ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) Ba dòng đầu tiên, mỗi dòng số tự nhiên tương ứng n,u,vn,u,v (n≤105;u≤v≤109)(n≤105;u≤v≤109) Dòng thứ tư gồm một xâu SS gồm nn 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ứ ii là . nếu viên đá thứ ii không có hoa và là # nếu viên đá thứ ii 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≤100n≤100 Subtask 2 (25%): n≤1000n≤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ứ 33 đến vị trí thứ 88 hoặc từ vị trí thứ 44 đến vị trí thứ 99. Các chuỗi đá này có tỉ lệ số tảng đá có hoa là 46≥122064≥2012. 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ứ 44 đến vị trí thứ 88. Chuỗi đá này có tỉ lệ số tảng đá có hoa là 45≥162054≥2016. 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ứ 44 đến vị trí thứ 88 gồm toàn những tảng đá có hoa. Làm bằng python có giải thích!!!

Câu trả lời này dùng AI, hãy kiểm tra lại trước khi sử dụng

def max_stone_length(n, u, v, S):
max_length = 0

# Duyệt từ vị trí i đến j
for i in range(n):
flower_count = 0

for j in range(i, n):
if S[j] == '#':
flower_count += 1

total_length = j - i + 1
if flower_count v >= total_length u: # Kiểm tra tỉ lệ
max_length = max(max_length, total_length)
else:
break # Ngừng nếu không thỏa mãn điều kiện nữa

return max_length

# Nhập vào các giá trị từ bàn phím
n = int(input())
u = int(input())
v = int(input())
S = input().strip()

# Gọi hàm để tìm độ dài chuỗi đá dài nhất và in ra kết quả
result = max_stone_length(n, u, v, S)
print(result)

# Giải thích:
# - Hút̀ hoài hoàn hảó cho các bông hoa là thật ra không có nhiều.
# - Chúng ta sẽ chạy một vòng lặp từ trái sang phải để tìm các chuỗi đá.
# Trong một lặp, kiểm tra tất cả các vị trí được chọn từ vị trí hiện tại.
# - Đếm số bông hoa trong dải từ i đến j, và kiểm tra tỷ lệ.
# - Nếu tỷ lệ này lớn hơn hoặc bằng tỷ lệ yêu cầu, lưu độ dài này vào danh sách các độ dài max.
# - Khi phát hiện rằng tỷ lệ không kỳ vọng (chỉ dừng lại cho j), chúng ta có thể chuyển sang i mới mà không cần lặp lại.
# - Chương trình này chạy với độ phức tạp O(n^2) theo đường thẳng khi n <= 100, nhưng trong phần nhiều n >= 100 dạng khác nhau, cần cách tối ưu hơn.

Đăng phản hồi