use strict; { use integer; my @sizes; my %ans; my @align; sub group_cats { (my $num, @sizes) = @_; %ans = (); my $a = 1; for my $i (1..$#sizes) { if ($a + $a < $i) { $a += $a; } $align[$i] = $a; } $align[0] = 0; my ($size, @partition) = _group_cats($num, 0, $#sizes); return @partition; } sub _group_cats { my $key = join ":", @_; my ($num, $start, $end) = @_; if (not exists $ans{$key}) { if ($num < 1) { $ans{$key} = [0]; } elsif (1 == $num) { my @part = @sizes[$start..$end]; my $sum = 0; $sum += $_ for @part; $ans{$key} = [$sum, \@part]; } else { my $num_a = $align[$num]; my $num_b = $num - $num_a; my $min_mid = $start + $num_a - 1; my $max_mid = $end - $num_b; my $mid = $min_mid + $align[$max_mid - $min_mid]; my ($last_a, @part_a) = _group_cats($num_a, $start, $mid); my ($last_b, @part_b) = _group_cats($num_b, $mid + 1, $end); my $best = $last_a < $last_b ? $last_b : $last_a; my @best_part = (@part_a, @part_b); while ($min_mid < $max_mid) { if ($last_b <= $last_a) { if ($max_mid > $mid) { $max_mid = $mid; } else { $max_mid--; } } else { $min_mid = $mid; } $mid = $min_mid + $align[$max_mid - $min_mid]; ($last_a, @part_a) = _group_cats($num_a, $start, $mid); ($last_b, @part_b) = _group_cats($num_b, $mid + 1, $end); my $max = $last_a < $last_b ? $last_b : $last_a; if ($max < $best) { $best = $max; @best_part = (@part_a, @part_b); } } $ans{$key} = [$best, @best_part]; } } return @{$ans{$key}}; } }