Từ tập các bài có trên SPOJ (acm) 371. Boxes Mã bài: BOXES

English

Vietnamese

Có n cái hộp xếp theo vòng tròn đánh số 1..n (1 ≤ n ≤ 1000) theo chiều kim đồng hồ. Mỗi hộp chứa một số quả bóng, tổng số quả bóng không quá n.

Cần dịch chuyển các quả bóng sao cho mỗi hộp không chứa quá 1 quả. Mỗi bước, ta có thể di chuyển một quả bóng từ một hộp sang một trong hai hộp bên cạnh.

Tính số bước di chuyển ít nhất.

Dữ liệu

Dòng đầu tiên chứa t là số bộ test (t ≤ 20). Mỗi bộ test có dạng:

• Dòng đầu tiên: n - số hộp.

• Dòng thứ hai: n số nguyên không âm là số quả bóng trong các hộp

Kết quả

Với mỗi bộ test in ra số bước ít nhất cần thiết.

Ví dụ

Dữ liệu
1
12
0 0 2 4 3 1 0 0 0 0 0 1

Kết quả
19

---

Được gửi lên bởi:	Ngô Minh Đức
Ngày:	2005-05-31
Thời gian chạy:	50s
Giới hạn mã nguồn:	50000B
Ngôn ngữ cho phép:	Tất cả ngoại trừ: AWK CLOJ ERL F# GO JS PERL 6 PYTH 3.1.2 SCALA SED TCL
Nguồn bài:	III Polish Olympiad in Informatics, stage 3