2015/48.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.16;
   4 use strict;
   5
   6 use List::Util qw(sum);
   7 chomp (my @packs = reverse <>);
   8 # my @packs = reverse(1 .. 5, 7 .. 11);
   9 my $size = sum @packs;
  10 $size /= 4;
  11 say "expect $size";
  12
  13 my $min = @packs;
  14 my $minqe;
  15
  16 sub divide {
  17         my ($s1, $s2, $s3, $l1, $qe, @rest) = @_;
  18         if ($s3 == $size) {
  19                 say "$s1 $s2 $s2 $l1 $qe";
  20                 if ($l1 < $min) {
  21                         $min = $l1;
  22                         $minqe = $qe;
  23                         say "min=$min, minqe=$qe";
  24                 } elsif ($l1 == $min && (!$minqe || $qe < $minqe)) {
  25                         $minqe = $qe;
  26                         say "minqe=$qe";
  27                 }
  28                 return;
  29         }
  30         for my $i (0 .. $#rest) {
  31                 my @nr = @rest;
  32                 my $n = splice (@nr, $i, 1);
  33                 if ($s1 < $size && $s1 + $n <= $size && $l1+1 <= $min) {
  34                         divide($s1+$n, 0, 0, $l1+1, $qe*$n, @nr);
  35                 } elsif ($s1 == $size && $s2 < $size && $s2 + $n <= $size
  36                         && ($l1 < $min || ($l1 == $min && $qe < $minqe))) {
  37                         # say "l2 $s1, $s2+$n, $l1, $qe";
  38                         divide($s1, $s2+$n, 0, $l1, $qe, @nr);
  39                 } elsif ($s1 == $size && $s2 == $size && $s3 < $size && $s3 + $n <= $size && ($l1 < $min || ($l1 == $min && $qe < $minqe))) {
  40                         divide($s1, $s2, $s3+$n, $l1, $qe, @nr);
  41                 }
  42         }
  43 }
  44
  45 divide(0, 0, 0, 0, 1, @packs);
  46 say $minqe;