Chuyển đá

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 2.0s
Memory limit: 64M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có ~N~ chiếc hộp trên 1 đường thẳng. Chiếc hộp thứ i có ~A_i~ viên sỏi.

Bạn cần phải di chuyển các viên sỏi giữa các hộp, sao cho lượng sỏi ở các hộp bằng nhau.

Việc di chuyển sỏi được diễn ra trong nhiều lượt, ở mỗi lượt, bạn có thể di chuyển các viên sỏi giữa các hộp kề nhau, theo như mô tả dưới đây:

  • Hộp ~i~ và hộp ~i+1~ được gọi là kề nhau. Như vậy, các hộp từ 2 đến ~N-1~ có đúng 2 hộp kề nó. Hộp 1 và hộp ~N~ chỉ kề với 1 hộp

  • Ở mỗi lượt, với mỗi hộp ~i~, bạn được chuyển nhiều nhất 1 viên sỏi sang mỗi hộp kề nó (với hộp ~i~, bạn có thể chuyển tối đa 2 viên sỏi sang 2 hộp kề nó, 1 viên sang hộp ~i-1~ và 1 viên sang hộp ~i+1~).

  • Việc chuyển đá ở mỗi lượt diễn ra đồng thời. Nghĩa là, bạn không thể chuyển viên đá từ hộp 1 sang hộp 2, rồi trong cùng lượt đó chuyển viên đá từ hộp 2 sang hộp 3.

Nhiệm vụ của bạn là tìm số lượt chuyển ít nhất.

Input

Gồm nhiều bộ test, kết thúc bởi số -1.

Mỗi bộ test gồm:

  • Dòng 1: ~N~

  • Một số dòng tiếp theo: ~N~ số nguyên dương, số thứ ~i~ là số viên sỏi trong hộp thứ ~i~.

Output

Nếu không thể chuyển sao cho các hộp có số viên sỏi bằng nhau, in ra -1, ngược lại, in ra số lượt ít nhất.

Sample Input

3
0 99 3

2
49 50

8
16 17 15 0 20 1 1 2

10
0 0 100 0 0 0 0 0 0 0

4
4 0 0 0

-1

Sample Output

34
-1
23
70
3

Note

Ngoài test ví dụ, bài gồm 2 test.

  • Test 1: ~N < 25~
  • Test 2: ~N < 10,000~

~Ai \le 10^9~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.