Весёлые качели
(Время: 1 сек. Память: 32 Мб Сложность: 32%)
Однажды во дворе многоэтажки родители для своих n детей построили большие и прочные качели типа «качалка-балансир» в виде длинной балки, подвешенной в центре тяжести на шарнире так, что она может качаться в вертикальной плоскости.
Оказалось, что качаться на этих качелях интересно, когда качели уравновешены, то есть если модуль суммы моментов детей слева от центра качелей совпадает с модулем суммы моментов детей справа от центра. Напомним, что момент ребёнка равен произведению его массы на расстояние от него до центра качелей.
По заданной массе детей требуется выбрать им места на качелях так, чтобы все они сидели в различных позициях на целочисленном расстоянии от центра качелей и могли интересно качаться, то есть качели должны быть уравновешены. При этом никакой ребенок не должен сидеть в центре качелей.
Более формально: для каждого ребёнка номер i с массой mi необходимо определить целое число di (di ≠ 0) – его позицию на качелях так, чтобы все di были различны и выполнялось равенство:
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 1000) – количество детей.
Во второй строке заданы n целых чисел m1, m2, …, mn (1 ≤ mi ≤ 100), где mi обозначает массу i-го ребёнка в килограммах.
Выходные данные
В выходной файл OUTPUT.TXT выведите «No», если решения не существует. В противном случае в первой строке выведите «Yes», а во второй строке – последовательность различных целых чисел di (1 ≤ |di| ≤ 109). Если существует несколько решений, выведите любое.
Гарантируется, что если решение существует, то найдётся и решение для |di| ≤ 109 при всех i.
Примеры
№ | INPUT.TXT | OUTPUT.TXT | Пояснение |
1 | 1 1 | No | Нет решения |
2 | 2 3 8 | Yes -8 3 | 3∙(–8) + 8∙3 = –24 + 24 = 0 |
3 | 5 1 2 3 4 2 | Yes 5 -10 13 -8 4 | 1∙5 + 2∙(–10) + 3∙13 + 4∙(–8) + 2∙4 = 0 |
Система оценки
Решения, работающие только для случаев, когда присутствует хотя бы один ребёнок с массой в 1 килограмм, будут оцениваться в 50 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|