HSG THPT Hải Phòng 2022 - Bài 3
View as PDF
Trang trại gà của nhà Bé Bo có ~n~ con gà siêu trứng đánh số từ ~1~ đến ~n~. Con gà ~i~ ~(1 \le i \le n)~ đẻ quả trứng đầu tiên ở giây ~p_i~, sau đó cứ ~t_i~ giây tiếp theo sẽ đẻ thêm một quả trứng.
Yêu cầu: Bạn hãy viết chương trình tính thời gian nhỏ nhất (tính bằng giây) để Bé Bo thu được ít nhất ~x~ quả trứng.
Input
- Dòng thứ nhất chứa hai số nguyên dương ~n, x~;
- ~n~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le n)~ chứa hai số nguyên dương ~p_i~, ~t_i~ (~1 \le p_i, t_i \le 500~).
Output
Ghi ra một số nguyên duy nhất là thời gian nhỏ nhất để Bé Bo thu được ít nhất ~x~ quả trứng.
Scoring
Scoring table:
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20\%~ | ~n = 1~, ~x \le 10^{15}~ |
| 2 | ~45\%~ | ~n \le 20~, ~x \le 1000~ |
| 3 | ~35\%~ | ~n \le 20~, ~x \le 10^{15}~ |
Sample Input 1
2 3
10 30
5 25
Sample Output 1
30
Sample Input 2
2 3
10 5
5 10
Sample Output 2
15
Notes
Ở ví dụ đầu tiên:
Con gà số ~1~ đẻ quả trứng đầu tiên ở giây ~10~, đẻ quả trứng thứ ~2~ ở giây ~40~, quả trứng thứ ~3~ ở giây ~70~, ...
Con gà số ~2~ đẻ quả trứng đầu tiên ở giây ~5~, đẻ quả trứng thứ ~2~ ở giây ~30~, quả trứng thứ ~3~ ở giây ~55~, ...
Vậy chỉ sau ~30~ giây thì tổng số trứng thu được là ~3~ quả.
Ở ví dụ thứ hai:
Con gà số ~1~ đẻ quả trứng đầu tiên ở giây ~10~, đẻ quả trứng thứ ~2~ ở giây ~15~, ...
Con gà số ~2~ đẻ quả trứng đầu tiên ở giây ~5~, đẻ quả trứng thứ ~2~ ở giây ~15~, ...
Vậy:
Tổng số trứng thu được sau ~5~ giây: ~1~
Tổng số trứng thu được sau ~10~ giây: ~2~
Tổng số trứng thu được sau ~15~ giây: ~4~
Comments
Biến đổi một chút về cấp số cộng, nhận thấy việc tìm kiếm sẽ diễn ra trên khoảng từ 1 đến 10 mũ 15 * 500 (thời gian lớn nhất nếu x = 10^15 và t = 500 ), ta muốn tìm một số thời gian nhỏ nhất mà qua thời gian đó có được x quả trứng => Tư tưởng của binary search , làm từ l = 1 đến r = 10*15 * 500 là rara
kill con đề này trong 2 tiếng đúng 100% thi ở hn không biết được kk không nhỉnhỉ
số giây thì lớn hơn số trứng x còn j
This comment is hidden due to too much negative feedback. Show it anyway.