Решение задачи Парад с Codeforces
Без пояснения   Просмотров: 101
Совсем скоро в Берляндии состоится парад победы над инопланетными захватчиками. К сожалению, в войне погибли все солдаты, и теперь армия состоит исключительно из новобранцев, многие из которых даже не знают, с какой ноги начинается марш. Гражданское население тоже плохо понимает, с какой ноги начинается марш, поэтому важно лишь, чтобы как можно больше солдат шли в одну ногу.
В параде будут принимать участие n пеших колонн, i-я из которых состоит из l i солдат, начинающих марш с левой ноги, и r i солдат, начинающих марш с правой ноги.
Красота парада вычисляется по следующей формуле: если L — это суммарное количество солдат на параде, начинающих марш с левой ноги, а R — это суммарное количество солдат на параде, начинающих марш с правой ноги, то красота будет равна |L - R|.
Вы можете выбрать не более чем одну колонну, и изменить с какой ноги начинают марш все солдаты данной колонны. Формально, разрешается не более одного раза выбрать какой-то индекс i и поменять местами значения l i и r i.
Найдите номер колонны, при смене шага в которой красота парада станет максимально возможной, или определите, что такой операцией улучшить красоту парада нельзя.
В параде будут принимать участие n пеших колонн, i-я из которых состоит из l i солдат, начинающих марш с левой ноги, и r i солдат, начинающих марш с правой ноги.
Красота парада вычисляется по следующей формуле: если L — это суммарное количество солдат на параде, начинающих марш с левой ноги, а R — это суммарное количество солдат на параде, начинающих марш с правой ноги, то красота будет равна |L - R|.
Вы можете выбрать не более чем одну колонну, и изменить с какой ноги начинают марш все солдаты данной колонны. Формально, разрешается не более одного раза выбрать какой-то индекс i и поменять местами значения l i и r i.
Найдите номер колонны, при смене шага в которой красота парада станет максимально возможной, или определите, что такой операцией улучшить красоту парада нельзя.