Cho một hệ thống thời gian gồm giờ trong một ngày, được đánh số từ đến . Một ngày bắt đầu tại thời điểm và các giờ hoạt động theo quy tắc số dư (modulo ).
Bạn cần thực hiện giấc ngủ liên tiếp. Giấc ngủ thứ () có độ dài dự kiến là . Với mỗi giấc ngủ thứ , bạn có quyền lựa chọn thực hiện một trong hai phương án về thời gian ngủ:
Ngủ chính xác giờ.
Ngủ chính xác giờ.
Giả sử thời điểm bắt đầu giấc ngủ thứ là , thì thời điểm thức dậy sẽ được tính bằng:
Phương án 1:
Phương án 2:
Biết rằng thời điểm bắt đầu của giấc ngủ đầu tiên () là . Một giấc ngủ thứ được định nghĩa là "tốt" nếu thời điểm thức dậy thỏa mãn điều kiện .
Yêu cầu: Hãy tìm cách chọn phương án cho từng giấc ngủ trong số giấc ngủ sao cho tổng số lượng giấc ngủ "tốt" đạt giá trị lớn nhất.
Dữ liệu:
Dòng đầu tiên chứa bốn số nguyên (; ).
Dòng thứ hai chứa số nguyên ().
Kết quả:
In ra một số nguyên duy nhất là số lượng giấc ngủ "tốt" tối đa có thể đạt được.
Ví dụ:
Dữ liệu:
7 24 21 23
16 17 14 20 20 11 22
Kết quả:
3
Giải thích:
Một trong các phương án tối ưu là:
Giấc 1: Chọn . Thời điểm thức dậy: . (Không tốt)
Giấc 2: Chọn . Thời điểm thức dậy: . (Không tốt)
Giấc 3: Chọn . Thời điểm thức dậy: . (Tốt, vì )
Giấc 4: Chọn . Thời điểm thức dậy: . (Không tốt)
Giấc 5: Chọn . Thời điểm thức dậy: . (Không tốt)
Giấc 6: Chọn . Thời điểm thức dậy: . (Tốt, vì )
Giấc 7: Chọn . Thời điểm thức dậy: . (Tốt, vì )
Tổng số giấc ngủ tốt là 3.
Dữ liệu:
5 10 3 6
2 2 2 2 2
Kết quả:
3
Giới hạn:
Subtask #1 (20% số điểm): .
Subtask #2 (20% số điểm): .
Subtask #3 (20% số điểm): .
Subtask #4 (40% số điểm): Không có ràng buộc bổ sung ().
