#!/usr/bin/perl
use strict;
use warnings;
my @DATA;
while(<DATA>) { # Получение входных данных и запуск рабочей процедуры на них
next if @DATA < 3; # Не обрабатываем строки с менее чем 3 элементами
work();
}
sub work {
# Массив позиций разделителей с дополнительныйми элементами по краям
# для контроля по ним выходов за границы массива (сокращает количество проверок границ)
# Содержит начало данных, левый разделитель (после первого элемента),
# правый разделитель (второй с конца), конец данных
my $border = [ 0, 1, @DATA-1, @DATA-0 ];
# Текущие суммы разделенных частей массива, в тех же элементах (по номеру) что и позиции границ
my $sum = [ 0, $DATA[0], 0, $DATA[$border->[2]] ];
# Вычисляем сумму элементов средней части (массива без крайних элементов)
$sum->[2]+=$_ for @DATA[1..$border->[2]-1];
# Рабочий цикл, боюсь делать while(1)
for(1..1000) {
my $ch = change($border, $sum, 1) + # Двигаем левый разделитель
change($border, $sum, 2); # Двигаем правый разделитель
last unless $ch; # Завершаем цикл если ни одна граница не двигалась
}
# Печать результата
print join('+', @DATA[0..$border->[1]-1]), "=$sum->[1] // "; print join('+', @DATA[$border->[1]..$border->[2]-1]), "=$sum->[2] // "; print join('+', @DATA[$border->[2]..@DATA-1]), "=$sum->[3]\n"; }
sub change {
# Движение одного разделителя в сторону "улучшения равномерности сумм"
# Параметры: Описания границ, Текущие суммы, Номер разделителя
my($border, $sum, $pos) = @_;
my $n1 = $sum->[$pos]; # Сумма левее разделителя
my $n2 = $sum->[$pos+1]; # Сумма правее разделителя
# Получаем направление движения границы +1 вправо, -1 влево
# Если суммы одинаковы, направление 0 - выходим
(my $sign = $n2 <=> $n1) || return 0; my $i = $border->[$pos]; # Текущая позиция в массиве данных
# Выходим если движение в нужную сторону не возможно, так как упираемся в другой разделитель
return 0 if $border->[$pos+$sign] == $i+$sign; my $oldDelta = abs($n1 - $n2); # Текущая разница сумм if($sign > 0) { # движение вправо
$n1 += $DATA[ $i ];
$n2 -= $DATA[ $i ];
} else { # движение влево
$n1 -= $DATA[ $i-1 ];
$n2 += $DATA[ $i-1 ];
}
my $newDelta = abs($n1 - $n2); # Новая разность сумм # print "pos: $pos [$border->[$pos]], sign: $sign n1: $n1, n2: $n2 nD: $newDelta, oD: $oldDelta\n";
return 0 if $newDelta >= $oldDelta; # Выходим ничего не меняя, если результат не улучшился # Движение в выбранную сторону улучшает результат, сохраняем новые суммы и позицию
$sum->[$pos] = $n1;
$sum->[$pos+1] = $n2;
$border->[$pos]+=$sign;
}
__DATA__
1 2 3 100
1 2 3 100 101 102 140
4 4 4 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 100 1 1 1 1 1 1 1 1 1 1 200 1 1
IyEvdXNyL2Jpbi9wZXJsCnVzZSBzdHJpY3Q7CnVzZSB3YXJuaW5nczsKCm15IEBEQVRBOwp3aGlsZSg8REFUQT4pIHsgIyDQn9C+0LvRg9GH0LXQvdC40LUg0LLRhdC+0LTQvdGL0YUg0LTQsNC90L3Ri9GFINC4INC30LDQv9GD0YHQuiDRgNCw0LHQvtGH0LXQuSDQv9GA0L7RhtC10LTRg9GA0Ysg0L3QsCDQvdC40YUKICAgICAgICBjaG9tcDsKICAgICAgICBAREFUQSA9IHNwbGl0IC9ccysvOwogICAgICAgIG5leHQgaWYgQERBVEEgPCAzOyAjINCd0LUg0L7QsdGA0LDQsdCw0YLRi9Cy0LDQtdC8INGB0YLRgNC+0LrQuCDRgSDQvNC10L3QtdC1INGH0LXQvCAzINGN0LvQtdC80LXQvdGC0LDQvNC4CiAgICAgICAgd29yaygpOwp9CgpzdWIgd29yayB7CiAgICAgICAgIyDQnNCw0YHRgdC40LIg0L/QvtC30LjRhtC40Lkg0YDQsNC30LTQtdC70LjRgtC10LvQtdC5INGBINC00L7Qv9C+0LvQvdC40YLQtdC70YzQvdGL0LnQvNC4INGN0LvQtdC80LXQvdGC0LDQvNC4INC/0L4g0LrRgNCw0Y/QvAogICAgICAgICMg0LTQu9GPINC60L7QvdGC0YDQvtC70Y8g0L/QviDQvdC40Lwg0LLRi9GF0L7QtNC+0LIg0LfQsCDQs9GA0LDQvdC40YbRiyDQvNCw0YHRgdC40LLQsCAo0YHQvtC60YDQsNGJ0LDQtdGCINC60L7Qu9C40YfQtdGB0YLQstC+INC/0YDQvtCy0LXRgNC+0Log0LPRgNCw0L3QuNGGKQogICAgICAgICMg0KHQvtC00LXRgNC20LjRgiDQvdCw0YfQsNC70L4g0LTQsNC90L3Ri9GFLCDQu9C10LLRi9C5INGA0LDQt9C00LXQu9C40YLQtdC70YwgKNC/0L7RgdC70LUg0L/QtdGA0LLQvtCz0L4g0Y3Qu9C10LzQtdC90YLQsCksCiAgICAgICAgIyDQv9GA0LDQstGL0Lkg0YDQsNC30LTQtdC70LjRgtC10LvRjCAo0LLRgtC+0YDQvtC5INGBINC60L7QvdGG0LApLCDQutC+0L3QtdGGINC00LDQvdC90YvRhQogICAgICAgIG15ICRib3JkZXIgPSBbIDAsIDEsIEBEQVRBLTEsIEBEQVRBLTAgXTsKICAgICAgICAjINCi0LXQutGD0YnQuNC1INGB0YPQvNC80Ysg0YDQsNC30LTQtdC70LXQvdC90YvRhSDRh9Cw0YHRgtC10Lkg0LzQsNGB0YHQuNCy0LAsINCyINGC0LXRhSDQttC1INGN0LvQtdC80LXQvdGC0LDRhSAo0L/QviDQvdC+0LzQtdGA0YMpINGH0YLQviDQuCDQv9C+0LfQuNGG0LjQuCDQs9GA0LDQvdC40YYKICAgICAgICBteSAkc3VtID0gWyAwLCAkREFUQVswXSwgMCwgJERBVEFbJGJvcmRlci0+WzJdXSBdOwogICAgICAgICMg0JLRi9GH0LjRgdC70Y/QtdC8INGB0YPQvNC80YMg0Y3Qu9C10LzQtdC90YLQvtCyINGB0YDQtdC00L3QtdC5INGH0LDRgdGC0LggKNC80LDRgdGB0LjQstCwINCx0LXQtyDQutGA0LDQudC90LjRhSDRjdC70LXQvNC10L3RgtC+0LIpCiAgICAgICAgJHN1bS0+WzJdKz0kXyBmb3IgQERBVEFbMS4uJGJvcmRlci0+WzJdLTFdOwogICAgICAgICMg0KDQsNCx0L7Rh9C40Lkg0YbQuNC60LssINCx0L7RjtGB0Ywg0LTQtdC70LDRgtGMIHdoaWxlKDEpCiAgICAgICAgZm9yKDEuLjEwMDApIHsKICAgICAgICAgICAgICAgIG15ICRjaCA9IGNoYW5nZSgkYm9yZGVyLCAkc3VtLCAxKSArICMg0JTQstC40LPQsNC10Lwg0LvQtdCy0YvQuSDRgNCw0LfQtNC10LvQuNGC0LXQu9GMCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNoYW5nZSgkYm9yZGVyLCAkc3VtLCAyKTsgICMg0JTQstC40LPQsNC10Lwg0L/RgNCw0LLRi9C5INGA0LDQt9C00LXQu9C40YLQtdC70YwKICAgICAgICAgICAgICAgIGxhc3QgdW5sZXNzICRjaDsgIyDQl9Cw0LLQtdGA0YjQsNC10Lwg0YbQuNC60Lsg0LXRgdC70Lgg0L3QuCDQvtC00L3QsCDQs9GA0LDQvdC40YbQsCDQvdC1INC00LLQuNCz0LDQu9Cw0YHRjAogICAgICAgIH0KICAgICAgICAjINCf0LXRh9Cw0YLRjCDRgNC10LfRg9C70YzRgtCw0YLQsAogICAgICAgIHByaW50IGpvaW4oJysnLCBAREFUQVswLi4kYm9yZGVyLT5bMV0tMV0pLCAiPSRzdW0tPlsxXSAvLyAiOwogICAgICAgIHByaW50IGpvaW4oJysnLCBAREFUQVskYm9yZGVyLT5bMV0uLiRib3JkZXItPlsyXS0xXSksICI9JHN1bS0+WzJdIC8vICI7CiAgICAgICAgcHJpbnQgam9pbignKycsIEBEQVRBWyRib3JkZXItPlsyXS4uQERBVEEtMV0pLCAiPSRzdW0tPlszXVxuIjsKfQoKc3ViIGNoYW5nZSB7CiAgICAgICAgIyDQlNCy0LjQttC10L3QuNC1INC+0LTQvdC+0LPQviDRgNCw0LfQtNC10LvQuNGC0LXQu9GPINCyINGB0YLQvtGA0L7QvdGDICLRg9C70YPRh9GI0LXQvdC40Y8g0YDQsNCy0L3QvtC80LXRgNC90L7RgdGC0Lgg0YHRg9C80LwiCiAgICAgICAgIyDQn9Cw0YDQsNC80LXRgtGA0Ys6INCe0L/QuNGB0LDQvdC40Y8g0LPRgNCw0L3QuNGGLCDQotC10LrRg9GJ0LjQtSDRgdGD0LzQvNGLLCDQndC+0LzQtdGAINGA0LDQt9C00LXQu9C40YLQtdC70Y8KICAgICAgICBteSgkYm9yZGVyLCAkc3VtLCAkcG9zKSA9IEBfOwogICAgICAgIG15ICRuMSA9ICRzdW0tPlskcG9zXTsgICAjINCh0YPQvNC80LAg0LvQtdCy0LXQtSDRgNCw0LfQtNC10LvQuNGC0LXQu9GPCiAgICAgICAgbXkgJG4yID0gJHN1bS0+WyRwb3MrMV07ICMg0KHRg9C80LzQsCDQv9GA0LDQstC10LUg0YDQsNC30LTQtdC70LjRgtC10LvRjwogICAgICAgICMg0J/QvtC70YPRh9Cw0LXQvCDQvdCw0L/RgNCw0LLQu9C10L3QuNC1INC00LLQuNC20LXQvdC40Y8g0LPRgNCw0L3QuNGG0YsgKzEg0LLQv9GA0LDQstC+LCAtMSDQstC70LXQstC+CiAgICAgICAgIyDQldGB0LvQuCDRgdGD0LzQvNGLINC+0LTQuNC90LDQutC+0LLRiywg0L3QsNC/0YDQsNCy0LvQtdC90LjQtSAwIC0g0LLRi9GF0L7QtNC40LwKICAgICAgICAobXkgJHNpZ24gPSAkbjIgPD0+ICRuMSkgfHwgcmV0dXJuIDA7CiAgICAgICAgbXkgJGkgPSAkYm9yZGVyLT5bJHBvc107ICMg0KLQtdC60YPRidCw0Y8g0L/QvtC30LjRhtC40Y8g0LIg0LzQsNGB0YHQuNCy0LUg0LTQsNC90L3Ri9GFCiAgICAgICAgIyDQktGL0YXQvtC00LjQvCDQtdGB0LvQuCDQtNCy0LjQttC10L3QuNC1INCyINC90YPQttC90YPRjiDRgdGC0L7RgNC+0L3RgyDQvdC1INCy0L7Qt9C80L7QttC90L4sINGC0LDQuiDQutCw0Log0YPQv9C40YDQsNC10LzRgdGPINCyINC00YDRg9Cz0L7QuSDRgNCw0LfQtNC10LvQuNGC0LXQu9GMCiAgICAgICAgcmV0dXJuIDAgaWYgJGJvcmRlci0+WyRwb3MrJHNpZ25dID09ICRpKyRzaWduOwogICAgICAgIG15ICRvbGREZWx0YSA9IGFicygkbjEgLSAkbjIpOyAgIyDQotC10LrRg9GJ0LDRjyDRgNCw0LfQvdC40YbQsCDRgdGD0LzQvAogICAgICAgIGlmKCRzaWduID4gMCkgeyAjINC00LLQuNC20LXQvdC40LUg0LLQv9GA0LDQstC+CiAgICAgICAgICAgICAgICAkbjEgKz0gJERBVEFbICRpIF07CiAgICAgICAgICAgICAgICAkbjIgLT0gJERBVEFbICRpIF07CiAgICAgICAgfSBlbHNlIHsgIyDQtNCy0LjQttC10L3QuNC1INCy0LvQtdCy0L4KICAgICAgICAgICAgICAgICRuMSAtPSAkREFUQVsgJGktMSBdOwogICAgICAgICAgICAgICAgJG4yICs9ICREQVRBWyAkaS0xIF07CiAgICAgICAgfQogICAgICAgIG15ICRuZXdEZWx0YSA9IGFicygkbjEgLSAkbjIpOyAgIyDQndC+0LLQsNGPINGA0LDQt9C90L7RgdGC0Ywg0YHRg9C80LwKIyAgICAgICBwcmludCAicG9zOiAkcG9zIFskYm9yZGVyLT5bJHBvc11dLCAgIHNpZ246ICRzaWduIG4xOiAkbjEsICBuMjogJG4yIG5EOiAkbmV3RGVsdGEsIG9EOiAkb2xkRGVsdGFcbiI7CiAgICAgICAgcmV0dXJuIDAgaWYgJG5ld0RlbHRhID49ICRvbGREZWx0YTsgIyDQktGL0YXQvtC00LjQvCDQvdC40YfQtdCz0L4g0L3QtSDQvNC10L3Rj9GPLCDQtdGB0LvQuCDRgNC10LfRg9C70YzRgtCw0YIg0L3QtSDRg9C70YPRh9GI0LjQu9GB0Y8KICAgICAgICAjINCU0LLQuNC20LXQvdC40LUg0LIg0LLRi9Cx0YDQsNC90L3Rg9GOINGB0YLQvtGA0L7QvdGDINGD0LvRg9GH0YjQsNC10YIg0YDQtdC30YPQu9GM0YLQsNGCLCDRgdC+0YXRgNCw0L3Rj9C10Lwg0L3QvtCy0YvQtSDRgdGD0LzQvNGLINC4INC/0L7Qt9C40YbQuNGOCiAgICAgICAgJHN1bS0+WyRwb3NdID0gJG4xOwogICAgICAgICRzdW0tPlskcG9zKzFdID0gJG4yOwogICAgICAgICRib3JkZXItPlskcG9zXSs9JHNpZ247CiAgICAgICAgcmV0dXJuIDE7Cn0KX19EQVRBX18KMSAyIDMgMTAwCjEgMiAzIDEwMCAxMDEgMTAyIDE0MAo0IDQgNCA0CjEgMSAxIDEgMSAxIDEgMSAxIDEgMSAxIDEgMSAxIDEgMSAxIDEgMSAxIDEKMSAxIDEgMSAxIDEgMSAxIDEwMCAxIDEgMSAxIDEgMSAxIDEgMSAxIDIwMCAxIDEKCg==