Bài 3 – Bình Dương 2021-2022 · Kho đề HSG Tin học 9

Đề bài

Bo quyết định mua nguyên liệu kết vòng tay để bán cho du khách. Đầu tiên, Bo vay tiền của bạn bè để mua nguyên liệu và khi bán được vòng tay sẽ trả lại tiền đã vay. Bo liệt kê tất cả $N$ các khoản tiền bán vòng tay và các khoản vay từ bạn bè trong sổ ghi chép được đánh số vị trí từ $1$ đến $N$ .

Khi có đủ tiền trả cho khoản vay thì Bo sẽ trả ngay cho người mình đang vay không nhất thiết phải bán hết vòng tay mới trả. Bo luôn bắt đầu ở vị trí $0$ và kết thúc phải là vị trí cuối cùng trong danh sách liệt kê. Hãy giúp Bo tìm số bước ngắn đi nhất để thu tiền bán vòng tay và trả tất cả nợ cho bạn bè. Trong trường hợp Bo không đủ tiền trả các khoản vay thì Bo quay về vị trí cuối cùng và vẫn còn nợ.

Dữ liệu vào

Dữ liệu vào: Số nguyên $N$ ( $1 \le N \le 10^5$ ) và $a_i$ số nguyên ( $-10^3 \le a_i \le 10^3$ )

Kết quả ra

Dữ liệu xuất: Một số nguyên duy nhất là số bước ngắn đi nhất Bo phải đi.

Ràng buộc

$1 \le N \le 10^5$ ;
$-10^3 \le a_i \le 10^3$ .

Ví dụ

Ví dụ 1

Dữ liệu vào

5
100 -200 250 -200 150

Kết quả ra

Giải thích

Bắt đầu 100 - 200 250 -200 150

Đi 1 đơn vị nhận được 100 (số bước: 1)
Đi tiếp 2 đơn vị nhận được 350 (số bước: 3)
Quay lại 1 đơn vị trả 200 còn lại 150 (số bước: 4)
Đi tiếp 3 đơn vị nhận được 150 (số bước: 7)
Quay lại 1 đơn vị và trả 200 (số bước: 8)

(Ghi chú: phần giải thích trong đề gốc dừng ở bước 8; bước thứ 9 là đi lại 1 đơn vị về vị trí cuối cùng.)

Ví dụ 2

Dữ liệu vào

5
100 -200 250 -200 10

Kết quả ra

Giải thích

Bắt đầu 100 - 200 250 -200 10

Đi 1 đơn vị nhận được 100 (số bước: 1)
Đi tiếp 2 đơn vị nhận được 350 (số bước: 3)
Quay lại 1 đơn vị trả 200 còn lại 150 (số bước: 4)
Đi tiếp 3 đơn vị nhận được 10 (số bước: 7)