Chế độ ăn cân bằng
Đề bài
Mô tả
Mỗi ngày, Danny mua một chiếc kẹo ở cửa hàng và ăn nó. Cửa hàng có loại kẹo, đánh số từ đến . Danny biết rằng một chế độ ăn cân bằng là quan trọng và áp dụng điều đó vào việc mua kẹo của mình. Với mỗi loại kẹo , anh gán một tỉ lệ mục tiêu là một số thực (). Anh muốn tỉ lệ kẹo loại trong số tất cả kẹo đã ăn xấp xỉ bằng . Chính xác hơn, gọi là số kẹo loại Danny đã ăn và . Tập kẹo được gọi là cân bằng nếu với mọi ta có
Danny đã mua và ăn kẹo được một thời gian, và trong suốt thời gian đó tập kẹo luôn cân bằng. Bây giờ anh tự hỏi mình còn có thể mua thêm bao nhiêu chiếc kẹo nữa mà vẫn giữ được điều kiện này. Cho các tỉ lệ mục tiêu và dãy kẹo anh đã ăn cho tới nay, hãy xác định anh có thể mua và ăn thêm nhiều nhất bao nhiêu chiếc kẹo sao cho tại mọi thời điểm tập kẹo đều cân bằng.
Dữ liệu vào
Dữ liệu vào gồm ba dòng:
- Dòng đầu tiên chứa hai số nguyên là số loại kẹo và là số kẹo Danny đã ăn.
- Dòng thứ hai chứa số nguyên dương . Các số này tỉ lệ với , tức là .
- Dòng thứ ba chứa số nguyên , trong đó là loại kẹo Danny đã mua và ăn vào ngày thứ (dòng này rỗng khi ).
Dữ liệu ra
In ra số kẹo nhiều nhất Danny có thể mua và ăn thêm mà chế độ ăn vẫn luôn cân bằng. Nếu số kẹo không có giới hạn trên, in ra từ forever.
Ràng buộc
- , .
- và .
- .
- Mọi tiền tố của dãy (kể cả toàn bộ dãy) đều cân bằng.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 5 2 1 6 3 5 3 1 2 5 3 5 |
1 | Tổng các là , đã ăn . Khi cần , và , tức là cần thêm ít nhất chiếc kẹo trong khi chỉ có ngày ( và ). Vậy chỉ ăn thêm được chiếc. |
| 6 4 2 1 6 3 5 3 1 2 5 3 |
forever | Từ trạng thái này Danny có thể ăn tiếp mãi mà tập kẹo luôn cân bằng. |
Bình luận