USACO Jan 2022 - Bronze - Drought

View as PDF
Submit solution
Problem ID: usaco_prob3_bronze_jan22
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Suggester:
DangHung845
Problem type
Allowed languages
C, C++, Java, Pascal, Perl, Python

Cỏ trên đồng của bác nông dân John đã bị khô héo do hạn hán. Sau thời gian tuyệt vọng và suy ngẫm, bác John nảy ra một ý tưởng tuyệt vời là mua ngô để nuôi những con bò yêu quí của mình.

Bác John có ~N~ con bò ~(1 \le N \le 10^5)~ được xếp thành ~1~ hàng sao con bò thứ ~i~ của hàng có mức đói là ~h_i~ ~(0 \le h_i \le 10^9)~. Vì bò là động vật xã hội và đòi ăn cùng nhau, nên cách suy nhất để bác John giảm mức đói cho đàn bò của mình là chọn hai con bò kế tiếp nhau lần lượt là con bò thứ ~i~ và thứ ~i + 1~ và cho mỗi con ăn một bao ngô, khi đó mức đói của mỗi con giảm đi ~1~.

Bác John muốn cho những con bò ăn cho đến khi tất cả con bò có cùng mức đói và mức đói là số nguyên không âm. Hãy giúp bác John xác định số lượng bao ngô tối thiểu mà bác cần cho đàn bò ăn, in ra ~-1~ nếu không có cách giải quyết.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 100)~ tương ứng với số test case.
  • Mỗi test case gồm 2 dòng: dòng đầu tiên chứa số nguyên ~N~, dòng thứ hai chứa dãy số nguyên ~h_1, h_2, ..., h_N~.

    • Đảm bảo rằng tổng của các số nguyên ~N~ trong tất cả các test case đều không quá ~10^5~.

    Dữ liệu ra

    In ra ~T~ dòng, mỗi dòng tương ứng với một test case.

    Lưu ý: Vì số nguyên trong bài có thể có kích thước lớn nên yêu cầu dùng kiểu dữ liệu số nguyên ~64-~bit (ví dụ: long long trong C/C++).

    Sample Input

    5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9

    Sample Output

    14
16
-1
-1
-1

    Giải thích

  • Ở test case đầu tiên, cho ~2~ bao ngô cho con bò ~2~ và ~3~, sau đó cho ~5~ bao ngô cho con bò ~1~ và ~2~, kết quả mỗi con bò đều có mức đói là ~3~.
  • Ở test case thứ hai, cho ~2~ bao ngô cho cả hai con bò ~1~ và ~2~, ~2~ bao ngô cho con bò ~2~ và ~3~, ~2~ bao ngô cho con bò ~4~ và ~5~, và ~2~ bao ngô cho con bò ~5~ và ~6~, kết quả mỗi con bò đều có mức đói là ~2~.
  • Ở những test case còn lại, không có cách đều để mức đói của tất cả con bò bằng nhau.

    • Scoring

  • Bộ test ~2~ thoả mãn ~N \le 3~ và ~h_i \le 100~.
  • Bộ test ~3-8~ thoả mãn ~N \le 100~ và ~h_i \le 100~.
  • Bộ test ~9-14~ thoả mãn ~N \le 100~.
  • Bộ test ~15~ không ràng buộc gì thêm.

    • Ngoài ra, ~N~ luôn chẵn ở bộ test ~3-5~ và bộ test ~9-11~, ~N~ luôn lẻ ở bộ test ~6-8~ và bộ test ~12-14~.

    Nguồn bài: Arpan Banerjee


    Comments

    Please read the guidelines before commenting.

    There are no comments at the moment.