fork(1) download
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4.  
  5. my @DATA;
  6. while(<DATA>) { # Получение входных данных и запуск рабочей процедуры на них
  7. @DATA = split /\s+/;
  8. next if @DATA < 3; # Не обрабатываем строки с менее чем 3 элементами
  9. work();
  10. }
  11.  
  12. sub work {
  13. # Массив позиций разделителей с дополнительныйми элементами по краям
  14. # для контроля по ним выходов за границы массива (сокращает количество проверок границ)
  15. # Содержит начало данных, левый разделитель (после первого элемента),
  16. # правый разделитель (второй с конца), конец данных
  17. my $border = [ 0, 1, @DATA-1, @DATA-0 ];
  18. # Текущие суммы разделенных частей массива, в тех же элементах (по номеру) что и позиции границ
  19. my $sum = [ 0, $DATA[0], 0, $DATA[$border->[2]] ];
  20. # Вычисляем сумму элементов средней части (массива без крайних элементов)
  21. $sum->[2]+=$_ for @DATA[1..$border->[2]-1];
  22. # Рабочий цикл, боюсь делать while(1)
  23. for(1..1000) {
  24. my $ch = change($border, $sum, 1) + # Двигаем левый разделитель
  25. change($border, $sum, 2); # Двигаем правый разделитель
  26. last unless $ch; # Завершаем цикл если ни одна граница не двигалась
  27. }
  28. # Печать результата
  29. print join('+', @DATA[0..$border->[1]-1]), "=$sum->[1] // ";
  30. print join('+', @DATA[$border->[1]..$border->[2]-1]), "=$sum->[2] // ";
  31. print join('+', @DATA[$border->[2]..@DATA-1]), "=$sum->[3]\n";
  32. }
  33.  
  34. sub change {
  35. # Движение одного разделителя в сторону "улучшения равномерности сумм"
  36. # Параметры: Описания границ, Текущие суммы, Номер разделителя
  37. my($border, $sum, $pos) = @_;
  38. my $n1 = $sum->[$pos]; # Сумма левее разделителя
  39. my $n2 = $sum->[$pos+1]; # Сумма правее разделителя
  40. # Получаем направление движения границы +1 вправо, -1 влево
  41. # Если суммы одинаковы, направление 0 - выходим
  42. (my $sign = $n2 <=> $n1) || return 0;
  43. my $i = $border->[$pos]; # Текущая позиция в массиве данных
  44. # Выходим если движение в нужную сторону не возможно, так как упираемся в другой разделитель
  45. return 0 if $border->[$pos+$sign] == $i+$sign;
  46. my $oldDelta = abs($n1 - $n2); # Текущая разница сумм
  47. if($sign > 0) { # движение вправо
  48. $n1 += $DATA[ $i ];
  49. $n2 -= $DATA[ $i ];
  50. } else { # движение влево
  51. $n1 -= $DATA[ $i-1 ];
  52. $n2 += $DATA[ $i-1 ];
  53. }
  54. my $newDelta = abs($n1 - $n2); # Новая разность сумм
  55. # print "pos: $pos [$border->[$pos]], sign: $sign n1: $n1, n2: $n2 nD: $newDelta, oD: $oldDelta\n";
  56. return 0 if $newDelta >= $oldDelta; # Выходим ничего не меняя, если результат не улучшился
  57. # Движение в выбранную сторону улучшает результат, сохраняем новые суммы и позицию
  58. $sum->[$pos] = $n1;
  59. $sum->[$pos+1] = $n2;
  60. $border->[$pos]+=$sign;
  61. return 1;
  62. }
  63. __DATA__
  64. 604 126 596 558 479 633 991 276 818 781 430 748 66 273 97 171 162 220 915 863 979 759 747 865 582 686 591 641 314 380 297 673 692 195 259 190 596 688 115 942 366 3 54 994 637 887 351 697 223 812 69 34 645 375 74 26 221 558 868 352 392 758 307 786 652 417 465 614 243 554 365 700 386 138 551 495 249 767 300 572 327 219 23 49 55 79 81 953 749 77 742 727 110 17 736 137 913 259 800 5
  65.  
Success #stdin #stdout 0.01s 5360KB
stdin
Standard input is empty
stdout
604+126+596+558+479+633+991+276+818+781+430+748+66+273+97+171+162+220+915+863+979+759+747+865+582+686+591+641=15657 // 314+380+297+673+692+195+259+190+596+688+115+942+366+3+54+994+637+887+351+697+223+812+69+34+645+375+74+26+221+558+868+352+392+758+307=15044 // 786+652+417+465+614+243+554+365+700+386+138+551+495+249+767+300+572+327+219+23+49+55+79+81+953+749+77+742+727+110+17+736+137+913+259+800+5=15312