- Mã:
- MAMA
- Tên:
- Ma cũ ma mới
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 4 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- nguoibian
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)
Ví dụ
- input4
3 2 4 1output7
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.
Theme :
Mời bạn soạn code
#include <iostream>using namespace std;struct ps { int tu, mau; &...