Hẹn Hò Valentine

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie muốn mời đúng một chàng bò trong số $N$ chàng bò đến dự vũ hội Valentine. Mỗi chàng bò $i$ có xác suất chấp nhận là $p_{i}$ (cho trước dưới dạng số nguyên $p_{i} \times 10^{6}$ ). Bessie sẽ mời tất cả các chàng bò trong một đoạn liên tiếp $[l, r]$ và muốn xác suất để đúng một chàng chấp nhận là lớn nhất có thể.

Dữ liệu vào

Dòng đầu: số nguyên $N$ ( $1 \leq N \leq 10^{6}$ )
$N$ dòng tiếp theo, dòng $i$ chứa số nguyên $p_{i} \times 10^{6}$ (với $0 < p_{i} < 1$ )

Dữ liệu ra

Một số nguyên: giá trị xác suất tối đa nhân $10^{6}$ , lấy phần nguyên (floor).

Ràng buộc

$1 \leq N \leq 10^{6}$
$0 < p_{i} \times 10^{6} < 10^{6}$

Ví dụ

Input	Output	Giải thích
3 300000 400000 350000	470000	Chọn đoạn $[2, 3]$ ( $p_{2} = 0.4$ , $p_{3} = 0.35$ ). Xác suất đúng một chàng chấp nhận $\approx 0.47$ .
1 500000	500000	Chỉ có một chàng bò với $p_{1} = 0.5$ , xác suất đúng một chấp nhận là $0.5$ .

Bình luận

Không có bình luận tại thời điểm này.