Bò nổi giận (Bronze)

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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ó $N$ kiện cỏ trên trục số, mỗi kiện ở vị trí $x_{i}$ . Bạn bắn một con bò vào một kiện cỏ, khiến nó nổ tung. Khi một kiện nổ, nó có bán kính nổ phụ thuộc vào bước thời gian:

Bước 1: kiện bắt đầu nổ có bán kính $1$ .
Bước 2: các kiện bị kích nổ ở bước 1 có bán kính $2$ .
Bước $t$ : các kiện bị kích nổ ở bước $t - 1$ có bán kính $t$ .

Một kiện ở vị trí $y$ bị kích nổ bởi kiện ở vị trí $x$ với bán kính $r$ nếu $| x - y | \leq r$ .

Hãy tìm số kiện cỏ tối đa có thể nổ khi chọn kiện bắt đầu tối ưu.

Dữ liệu vào

Dòng đầu: số nguyên $N$ .
$N$ dòng tiếp theo: mỗi dòng một số nguyên $x_{i}$ .

Dữ liệu ra

Một số nguyên duy nhất — số kiện cỏ tối đa có thể nổ.

Ràng buộc

$1 \leq N \leq 100$
$0 \leq x_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
6 8 5 6 13 3 4	5	Bắn vào vị trí 5: nổ bán kính 1 → kích 4 và 6. Bước 2 bán kính 2 → kích 3 và 8. Vị trí 13 quá xa.

Bình luận

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