Решение задачи Три кучки с конфетами с Codeforces

Алиса и Боб получили три большие кучки конфет в качестве подарка. Теперь они хотят разделить эти конфеты между собой настолько честно, насколько это возможно. Чтобы сделать это, Алиса забирает одну кучку с конфетами себе, затем Боб забирает одну из других двух кучек себе. Последняя кучка делится между Алисой и Бобом так, как они хотят: например, возможно, что Алиса возьмет всю кучку себе, а Боб не получит из нее ничего.

После того как они возьмут все конфеты из кучек, если у Алисы будет больше конфет, чем у Боба, она выкидывает некоторые конфеты таким образом, что количество ее конфет становится равным количеству конфет Боба. Конечно, Боб сделает то же самое, если у него больше конфет.

Алиса и Боб хотят иметь как можно больше конфет каждый, и будут планировать процесс разделения конфет соответственно. Пожалуйста, посчитайте максимально возможное количество конфет, которое может оказаться у Алисы после процесса их разделения (конечно же, у Боба будет столько же конфет).

Вам необходимо ответить на q независимых запросов.

Рассмотрим следующий пример: [1,3,4]. Здесь Алиса может взять третью кучку, Боб может взять вторую кучу, и единственную оставшуюся конфету из первой кучки получает Боб — тогда у Алисы будет 4 конфеты и у Боба тоже будет 4 конфеты.

Другой возможный пример — это [1,10,100]. Тогда Алиса может выбрать вторую кучку, Боб может выбрать первую кучку, и конфеты из третьей кучки могут быть разделены таким образом, что Боб получит 54 конфеты, а Алиса получит 46 конфет. Теперь у Боба есть 55 конфет, а у Алисы — 56 конфет, таким образом, она должна выкинуть одну конфету — и после этого у нее будет также 55 конфет.