Tốc độ tàu tối thiểu
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Bạn cần đi $N$ chặng tàu liên tiếp, chặng thứ $i$ có độ dài $d_i$ km. Tàu chạy với cùng vận tốc nguyên dương $v$ (km/h) trên mọi chặng. Tuy nhiên, mỗi chuyến tàu chỉ khởi hành vào các giờ chẵn nguyên (tức sau khi hoàn thành chặng $i < N$, bạn phải làm tròn lên số giờ nguyên gần nhất để chờ chuyến tiếp theo; riêng chặng cuối $N$ không cần chờ). Cho tổng thời gian cho phép là $H$ giờ (số thực). Hãy tìm vận tốc nguyên dương $v$ nhỏ nhất ($1 \le v \le 10^7$) để đến nơi trong thời gian $\le H$, hoặc in ra -1 nếu không thể.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ và số thực $H$ (tối đa $2$ chữ số thập phân).
- Dòng thứ hai chứa $N$ số nguyên $d_1, d_2, \dots, d_N$.
Dữ liệu ra
- Một số nguyên duy nhất là vận tốc $v$ nhỏ nhất, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 3 2.7\n1 3 2 | 3 |
| 3 1.9\n1 3 2 | -1 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le d_i \le 10^5$, $1 \le H \le 10^9$
Community Discussion