Chuyển tiền giữa các ngân hàng
Đề bài
Mô tả
Trong thành phố có ngân hàng được xếp thành một vòng tròn: ngân hàng và ngân hàng là hàng xóm của nhau với mọi , và ngân hàng cũng là hàng xóm của ngân hàng (khi ). Không ngân hàng nào là hàng xóm của chính nó.
Vasya có một tài khoản ở mỗi ngân hàng. Số dư tài khoản có thể âm, nghĩa là Vasya đang nợ ngân hàng đó.
Chỉ có duy nhất một loại thao tác: chuyển một lượng tiền tuỳ ý từ tài khoản ở một ngân hàng sang tài khoản ở một ngân hàng hàng xóm. Không có giới hạn nào về lượng tiền được chuyển, và cũng không yêu cầu số dư phải không âm tại bất kỳ thời điểm nào.
Hãy tìm số thao tác ít nhất để đưa số dư của tất cả các tài khoản về .
Dữ liệu vào
- Dòng đầu chứa số nguyên là số ngân hàng.
- Dòng thứ hai chứa số nguyên , trong đó là số dư ban đầu của tài khoản ở ngân hàng thứ .
Dữ liệu đảm bảo tổng tất cả các bằng , nên luôn tồn tại đáp án.
Dữ liệu ra
In ra một số nguyên duy nhất: số thao tác ít nhất cần thực hiện.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 5 0 -5 |
1 | Ngân hàng 1 và ngân hàng 3 là hàng xóm (vòng tròn), nên chỉ cần chuyển 5 từ ngân hàng 1 sang ngân hàng 3. |
| 4 -1 0 1 0 |
2 | Chuyển 1 từ ngân hàng 3 sang ngân hàng 2, rồi chuyển 1 từ ngân hàng 2 sang ngân hàng 1. |
| 4 1 2 3 -6 |
3 | Chuyển 1 từ ngân hàng 1 sang ngân hàng 2, chuyển 3 từ ngân hàng 2 sang ngân hàng 3, chuyển 6 từ ngân hàng 3 sang ngân hàng 4. |
Bình luận
#include <iostream>
using namespace std;
int i,n;
int main(){
return 0;