pastebin

Paste Search Dynamic
Recent pastes
DATA
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4.  
  5. my @DATA;
  6. while(<DATA>) { # Получение входных данных и запуск рабочей процедуры на них
  7.         chomp;
  8.         @DATA = split /\s+/;
  9.         next if @DATA < 3; # Не обрабатываем строки с менее чем 3 элементами
  10.         work();
  11. }
  12.  
  13. sub work {
  14.         # Массив позиций разделителей с дополнительныйми элементами по краям
  15.         # для контроля по ним выходов за границы массива (сокращает количество проверок границ)
  16.         # Содержит начало данных, левый разделитель (после первого элемента),
  17.         # правый разделитель (второй с конца), конец данных
  18.         my $border = [ 0, 1, @DATA-1, @DATA-0 ];
  19.         # Текущие суммы разделенных частей массива, в тех же элементах (по номеру) что и позиции границ
  20.         my $sum = [ 0, $DATA[0], 0, $DATA[$border->[2]] ];
  21.         # Вычисляем сумму элементов средней части (массива без крайних элементов)
  22.         $sum->[2]+=$_ for @DATA[1..$border->[2]-1];
  23.         # Рабочий цикл, боюсь делать while(1)
  24.         for(1..1000) {
  25.                 my $ch = change($border, $sum, 1) + # Двигаем левый разделитель
  26.                                  change($border, $sum, 2);  # Двигаем правый разделитель
  27.                 last unless $ch; # Завершаем цикл если ни одна граница не двигалась
  28.         }
  29.         # Печать результата
  30.         print join('+', @DATA[0..$border->[1]-1]), "=$sum->[1] // ";
  31.         print join('+', @DATA[$border->[1]..$border->[2]-1]), "=$sum->[2] // ";
  32.         print join('+', @DATA[$border->[2]..@DATA-1]), "=$sum->[3]\n";
  33. }
  34.  
  35. sub change {
  36.         # Движение одного разделителя в сторону "улучшения равномерности сумм"
  37.         # Параметры: Описания границ, Текущие суммы, Номер разделителя
  38.         my($border, $sum, $pos) = @_;
  39.         my $n1 = $sum->[$pos];   # Сумма левее разделителя
  40.         my $n2 = $sum->[$pos+1]; # Сумма правее разделителя
  41.         # Получаем направление движения границы +1 вправо, -1 влево
  42.         # Если суммы одинаковы, направление 0 - выходим
  43.         (my $sign = $n2 <=> $n1) || return 0;
  44.         my $i = $border->[$pos]; # Текущая позиция в массиве данных
  45.         # Выходим если движение в нужную сторону не возможно, так как упираемся в другой разделитель
  46.         return 0 if $border->[$pos+$sign] == $i+$sign;
  47.         my $oldDelta = abs($n1 - $n2);  # Текущая разница сумм
  48.         if($sign > 0) { # движение вправо
  49.                 $n1 += $DATA[ $i ];
  50.                 $n2 -= $DATA[ $i ];
  51.         } else { # движение влево
  52.                 $n1 -= $DATA[ $i-1 ];
  53.                 $n2 += $DATA[ $i-1 ];
  54.         }
  55.         my $newDelta = abs($n1 - $n2);  # Новая разность сумм
  56. #       print "pos: $pos [$border->[$pos]],   sign: $sign n1: $n1,  n2: $n2 nD: $newDelta, oD: $oldDelta\n";
  57.         return 0 if $newDelta >= $oldDelta; # Выходим ничего не меняя, если результат не улучшился
  58.         # Движение в выбранную сторону улучшает результат, сохраняем новые суммы и позицию
  59.         $sum->[$pos] = $n1;
  60.         $sum->[$pos+1] = $n2;
  61.         $border->[$pos]+=$sign;
  62.         return 1;
  63. }
  64.  
Parsed in 0.019 seconds