Diễn tập đoàn xe tăng

Điểm: 5,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Một đoàn xe tăng gồm $n$ chiếc xếp thành hàng. Ban đầu các xe được đánh số từ $1$ tới $n$ theo thứ tự xuất hiện trong đoàn (xe $1$ đứng đầu, xe $n$ đứng cuối). Mỗi xe $i$ có một bán kính nhận tin $a_{i}$ .

Cuộc diễn tập gồm $n$ lượt truyền tin. Một lượt diễn ra như sau:

Xe đang đứng đầu đoàn phát một bản tin. Xe nhận được bản tin sẽ tiếp tục chuyển nó về phía cuối đoàn. Quá trình lặp lại cho đến khi xe đang đứng cuối đoàn nhận được bản tin.
Sau khi xe đang đứng cuối đoàn nhận bản tin, nó di chuyển lên đầu đoàn. Lúc này đoàn đã có một thứ tự mới và lượt tiếp theo bắt đầu.

Cuộc diễn tập kết thúc khi đoàn xe quay lại đúng thứ tự ban đầu, tức là sau lượt mà xe $1$ vừa di chuyển lên đầu đoàn.

Việc truyền tin giữa hai xe diễn ra như sau. Xét hai xe trong đoàn: xe thứ nhất đứng ở vị trí thứ $i$ tính từ đầu đoàn, xe thứ hai đứng ở vị trí thứ $j$ và có số hiệu là $x$ . Xe thứ nhất có thể truyền trực tiếp bản tin tới xe thứ hai khi và chỉ khi $i < j$ và $i \geq j - a_{x}$ . Mỗi lần truyền tin trực tiếp giữa hai xe mất đúng 1 giây. Không nhất thiết mọi xe trong đoàn phải nhận được bản tin trong một lượt — chỉ cần xe đang đứng cuối đoàn nhận được.

Cho trước $n$ và các bán kính nhận tin $a_{1}, a_{2}, \dots, a_{n}$ , hãy tổ chức việc truyền tin sao cho tổng thời gian truyền tin của cả $n$ lượt là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — số lượng xe trong đoàn.
$n$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $a_{i}$ — bán kính nhận tin của xe có số hiệu $i$ .

Dữ liệu ra

Một số nguyên duy nhất — tổng thời gian nhỏ nhất để truyền hết $n$ bản tin.

Ràng buộc

$2 \leq n \leq 250 000$
$1 \leq a_{i} \leq 250 000$

Ví dụ

Input	Output	Giải thích
3 2 1 1	5	Thứ tự ban đầu là $1, 2, 3$ . Lượt 1: xe $1$ → xe $2$ → xe $3$ (2 giây). Lượt 2 (thứ tự $3, 1, 2$ ): xe $3$ → xe $1$ → xe $2$ (2 giây). Lượt 3 (thứ tự $2, 3, 1$ ): xe $2$ truyền thẳng cho xe $1$ vì bán kính của xe $1$ đủ lớn (1 giây). Tổng cộng $5$ giây.
5 2 2 2 2 2	10	Mọi xe có bán kính $2$ . Trong mỗi lượt, truyền một bản tin tới cuối đoàn cần $2$ giây, nên $5$ lượt tốn tổng cộng $10$ giây.

Bình luận

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