HOMEWORK - Bài tập ngày Tết
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: middlest

Hùng là một học sinh giỏi, được nhiều bạn mến mộ. Thế nhưng, trong dịp Tết vừa qua, vì mải ăn món mứt dâu ngon tuyệt do mẹ cậu làm, kết quả là bị đau bụng suốt mấy ngày liền, khi cậu ta khỏi bệnh cũng chính là lúc hết Tết. Lúc này Hùng mới sực nhớ ra bài tập Tết mà thầy giao, bình thường đó chỉ là những bài tập cỏn con đối với Hùng, thế nhưng giờ đau bụng như thế này thì đến đọc đề còn không nỗi huống chi là làm :(( Các bạn NTUCoders hãy giúp Hùng giải bài tập để không bị thầy phạt ngày đầu năm nhé.

Đề bài như sau:

Cho dãy n số nguyên dương a1, a2, a3, .., an

Có thể thực hiện thao tác sau đây trên dãy:

- Chọn ra hai số bất kì trong dãy

- Giảm giá trị số lớn hơn đi một lượng bằng giá trị của số nhỏ hơn

Có thể thực hiện số lượng thao tác tùy ý thích sao cho tổng giá trị các phần tử của dãy là nhỏ nhất

Input

Dòng đầu tiên chứa số nguyên dương n (n <= 105)

Dòng tiếp theo chứa n số nguyên a1, a2, ..., an (1 <= ai <= 105)

Output

Một dòng duy nhất là tổng nhỏ nhất của dãy sau một số thao tác.

Ví dụ

  • input
    3
    4 2 1
    output
    3

Giải thích ví dụ

Với dãy số 4 2 1, ta lần lượt thực hiện các thao tác như sau

- Chọn số 4 và 2, giảm 4 đi 2, khi đó dãy trở thành 2 2 1

- Chọn số 2 và 1, giảm 2 đi 1, khi đó dãy trở thành 2 1 1

- Chọn số 2 và 1, giảm 2 đi 1, khi đó dãy trở thành 1 1 1

Lúc này không thể thực hiện thao tác được nữa do giá trị các phần tử trong dãy đều bằng nhau, tổng nhỏ nhất của dãy là 3

Back to Top