Задача G. Манускрипт
Задачу добавил: alef
Успешно сдано решений: 5
"Я был тогда молод и беден," - рассказывал Хасан, - "брался за любую работу..."Однажды один пожилой человек по имени Малик попросил его отнести в другой город своему родственнику Мураду старинную книгу, пообещав щедро вознаградить его. Но для этого Хасан должен был соблюсти одно условие - молчать всю дорогу. Хасан согласился и отправился в путь. Когда он достаточно далеко отошел от города, на его плечо вдруг сел ворон. Сколько Хасан ни пытался прогнать птицу, ворон не улетал. Так и пришел он к дому Мурада. Только тут ворон покинул его.
Мурад пригласил Хасана в дом, и плотно закрыв окна, достал из дорожного мешка книгу и положил ее на стол. Затем он открыл стоявший на столе ларец, и Хасан был на несколько секунд ослеплен блеском рубинов, лежавших в нем, - казалось, они сами излучали свет.
- Видишь два круга на обложке? - спросил Хасана Мурад. - Если правильно расположить в них камни, книга вновь сможет творить чудеса.
- А что значит - правильно? - поинтересовался Хасан.
Оказалось, что каждый из камней имеет свою магическую силу. Будучи положенным в еще пустой круг, он увеличивает свою магическую силу на единицу. Если камень добавляется в круг вторым, его магическая сила возрастает на 2, и так далее.
Правильное расположение - это такое расположение, при котором все камни из ларца будут положены в один или другой круг, и оба круга с камнями будут иметь одинаковую суммарную магическую силу.
- Попробуй разложить камни правильно, - предложил Мурад Хасану. - Конечно, это требует терпения, но ты потратишь время не зря...
Ваша задача - по заданному набору камней получить их правильное расположение или, если это невозможно, расположение, в котором суммарная магическая сила кругов отличается на минимально возможную величину.
Формат входного файла input.txt
Первая строка - целое число N (1 <= N <= 100) - количество рубинов в ларце
Вторая строка - N целых чисел через пробел M1, M2, ..., MN - магическая сила каждого из рубинов (1 <= Mj <= 100, j = 1, 2, ..., N)
Формат выходного файла output.txt
Будем называть круг "большим", если магическая сила камней в нем больше, чем в другом круге, или, при равной магической силе, в нем больше камней.
Первая строка - минимально возможная разница между магическими силами кругов.
Вторая строка - магическая сила камней и их количество (через пробел) в "большем" круге
Третья строка - магическая сила камней и их количество (через пробел) в "меньшем" круге
Пример входного файла
5
7 4 1 3 4
Пример выходного файла
0
14 3
14 2