MAMA - Ma cũ ma mới
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

       Có n con ma lần lượt gia nhập nghĩa trang theo thứ tự là 1, 2, 3,..., n. Chỉ số sức mạnh của các con ma tương ứng là a1, a2,..., an. Khi một con ma mới gia nhập nghĩa trang thì nó sẽ bị các con ma cũ bắt nạt. Giả sử con ma mới có chỉ số sức mạnh là M và con ma cũ có chỉ số sức mạnh là C, nếu M < C thì con ma mới phải nộp cho con ma cũ C - M đồng tiền vàng. Nếu M ≥ C thì thôi. Bạn hãy tính thử xem sau khi đủ n con ma gia nhập nghĩa trang thì các con ma phải đưa lẫn nhau tổng cộng bao nhiêu đồng tiền vàng?.

Dữ liệu nhập:

- Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 105)

- Dòng thứ hai là n số nguyên a1, a2, ..., an, mỗi số cách nhau một khoảng trắng (1 ≤ ai ≤ 109)  

Dữ liệu xuất:

- Là số nguyên xác định tổng cộng số đồng tiền vàng các con ma đưa lẫn nhau. Chỉ cần in ra 9 chữ số cuối (mod 109, nếu kết quả sau mod ít hơn 9 chữ số, không cần thêm số 0 ở đầu).

Ví dụ

  • input
    4
    3 2 4 1
    output
    7

Trong test 1:

1) Con ma 2 đưa cho con ma 3: 1 đồng tiền vàng.

2) Con ma 4: không đưa.

3) Con ma 1 đưa cho con ma 3 (2 đồng), con ma 2 (1 đồng), con ma 4 (3 đồng).

Tổng cộng 7 đồng.

Back to Top