eolymp
bolt
Try our new interface for solving problems
Məsələlər

Два капитана

Два капитана

\textit{Корабли без капитанов, капитан без корабля...} Несколько приятелей решили поиграть в футбол. Известно, что не все они играют одинаково хорошо, у каждого есть сила, которую можно выразить некоторым числом (чем больше число, тем сильнее игрок). Поэтому было решено выделить двух капитанов, которые будут набирать людей в команды. Сначала решили, что капитаны будут по очереди выбирать в свою команду по одному человеку. При этом изначально капитаны тянут жребий, и тот, кто его выигрывает, выбирает игрока первым. Однако получается, что при этом команда выигравшего жребий капитана оказывается гораздо сильнее другой команды, так как в каждой паре выбранных игроков игрок первой команды будет сильнее (по крайней мере, не слабее) игрока второй команды. Поэтому было решено поступить более справедливо. Капитаны, как и раньше, по очереди выбирают игроков, но при выборе первой пары (и каждой нечетной) выбирать начинает выигравший жребий капитан, а при выборе второй (и каждой четной) - первым выбирает другой, проигравший жребий, капитан. Однако в таком случае может получиться, что при оптимальном выборе игроков капитанами команда проигравшего жребий капитана окажется сильнее команды выигравшего жребий капитана. Вам необходимо определить, что выгодно - выиграть или проиграть жребий, чтобы набрать более сильную команду, при условии, что оба капитана будут действовать оптимально, то есть выберут стратегию, которая позволит им набрать настолько сильную команду, насколько это возможно, независимо от выбора капитана команды соперника. \InputFile В первой строке входного файла дано количество игроков \textbf{n} (\textbf{0} < \textbf{n} ≤ \textbf{100}, \textbf{n} - четное). Во второй строке перечислены \textbf{n} чисел \textbf{a_i} - силы игроков (\textbf{a_i} ≥ \textbf{0}). Капитанов среди них нет. Силы капитанов равны нулю. Все числа во входном файле целые и их сумма не превышает \textbf{10^9}. \OutputFile В первой строке выходного файла выведите, получится ли команда выигравшего жребий сильнее (\textbf{YES} - если получится, и \textbf{NO} - если не получится). Во второй строке выведите через пробел, какая сила команды получится у выигравшего жребий капитана, и какая сила команды получится у проигравшего жребий капитана. Сила команды - это сумма сил всех игроков этой команды.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4 
10 6 7 1
Çıxış verilənləri #1
NO
11 13
Mənbə Blitz Contest by SPbETU & Michael Dvorkin, Petrozavodsk Winter Training Session, January 31, 2006