Submit solution

Points: 0.89 (partial)
Time limit: 10.0s
Memory limit: 512M

Problem source:
III Polish Olympiad in Informatics, stage 3
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

Có ~n~ cái hộp xếp theo vòng tròn đánh số ~1~ ... ~n~ ~(1 \leq n \leq 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.

Input

Dòng đầu tiên chứa ~t~ là số bộ test ~(t \leq 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

Output

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

Sample Input

1
12
0 0 2 4 3 1 0 0 0 0 0 1

Sample Output

19

Comments

Please read the guidelines before commenting.



  • -2
    NSG  commented on 31, May, 2021, 22:33

    cho e hỏi bài này code cặp ghép o(n^3) có pass k ạ


    • 0
      I_love_Hoang_Yen  commented on 1, Jun, 2021, 9:09

      Cặp ghép N^3 của thầy Hoàng chạy nhanh như N^2 nên vẫn pass đc.


      • -3
        NSG  commented on 1, Jun, 2021, 10:52 edited

        em làm như thầy hoàng vẫn k pass huhu..