BOXES - Boxes
Giới hạn- Thời gian: 7.273s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: paulmcvn
- Nguồn bài: III Polish Olympiad in Informatics, stage 3