Thanh Cân Bằng

Đ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

Có một thanh cân bằng với $N + 2$ vị trí được đánh số từ $0$ đến $N + 1$ . Vị trí $0$ và $N + 1$ là hai đầu mút — nếu đến đó thì nhận được $0$ điểm thưởng.

Mỗi vị trí $k$ ( $1 \leq k \leq N$ ) có một giá trị thưởng $f (k) \geq 0$ . Tại mỗi bước, khi đứng ở vị trí $k$ , bạn có thể:

Nhảy xuống tại chỗ và nhận $f (k)$ điểm thưởng, hoặc
Tung đồng xu: với xác suất $1 / 2$ di chuyển sang trái (vị trí $k - 1$ ), với xác suất $1 / 2$ di chuyển sang phải (vị trí $k + 1$ ).

Mục tiêu là tối đa hóa kỳ vọng số điểm thưởng nhận được. Gọi $f^{*} (k)$ là kỳ vọng điểm thưởng tối ưu khi bắt đầu ở vị trí $k$ .

Với mỗi vị trí $k$ từ $1$ đến $N$ , hãy tính $⌊ f^{*} (k) \times 10^{5} ⌋$ .

Dữ liệu vào

Dòng 1: số nguyên $N$ ( $2 \leq N \leq 10^{5}$ )
$N$ dòng tiếp theo: giá trị $f (1), f (2), \dots, f (N)$ ( $0 \leq f (k) \leq 10^{9}$ )

Dữ liệu ra

$N$ dòng, dòng $k$ chứa $⌊ f^{*} (k) \times 10^{5} ⌋$ .

Ràng buộc

$2 \leq N \leq 10^{5}$
$0 \leq f (k) \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
2 1 3	150000 300000	Từ vị trí 1: nhảy ngay → 1; tung xu → kỳ vọng $(0 + 3) / 2 = 1.5$ . Vậy $f^{} (1) = 1.5$ . Từ vị trí 2: $f^{} (2) = max (3, (1.5 + 0) / 2) = 3$ . Xuất ra $⌊ 1.5 \times 10^{5} ⌋ = 150000$ và $300000$ .

Bình luận

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