Codeforces Round 228 (Div. 2) |
---|
Закончено |
Лиса Сиель играет с числами.
У Сиель есть n положительных целых чисел: x1, x2, ..., xn. Она может выполнять следующие операции столько раз, сколько ей нужно: выбрать два различных индекса i и j, таких, что выполняется условие xi > xj, а затем выполнить присвоение xi = xi - xj. Цель игры в том, чтобы сделать сумму всех чисел как можно меньше.
Пожалуйста, помогите Сиель найти эту минимальную сумму.
В первой строке содержится целое число n (2 ≤ n ≤ 100). Затем во второй строке записано n целых чисел: x1, x2, ..., xn (1 ≤ xi ≤ 100).
Выведите единственное целое число — требуемую минимальную сумму.
2
1 2
2
3
2 4 6
6
2
12 18
12
5
45 12 27 30 18
15
В первом примере оптимальный способ — выполнить присвоение: x2 = x2 - x1.
Во втором примере оптимальная последовательность операций такая: x3 = x3 - x2, x2 = x2 - x1.
Название |
---|