Tốc độ tàu tối thiểu

General
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$
Draft saved