#!/usr/bin/perl -w
use strict;

use Time::HiRes qw< time >;

$| = 1;
my( @Costs, @Trims );
for(  @ARGV  ) {
    my( $cost, $trim ) = /^(\d+)(\.\d+)$/ or die "Invalid cost.trim: $_\n";
    push @Costs, $cost;
    push @Trims, $trim;
}
my $Start = time();
my @order = sort {
    $Trims[$a]*$Costs[$a] <=> $Trims[$b]*$Costs[$b]
} 0..$#Costs;
@Trims = @Trims[@order];
@Costs = @Costs[@order];
print " $Costs[$_] $Trims[$_],"
    for  0..$#Costs;
print $/;
my @Win;
cost( \@Costs, \@Trims );
print $/;
print " $Costs[$_] $Trims[$_],"
    for  @Win;
printf "\n%.3f seconds\n", time() - $Start;

sub NextPermuteNum(\@)
{
    my( $vals )= @_;
    my $last= $#{$vals};
    return !1   if  $last < 1;
    while( 1 ) {
        # Find last item not in reverse-sorted order:
        my $i= $last-1;
        $i--   while  0 <= $i  &&  $vals->[$i+1] <= $vals->[$i];
        # If complete reverse sort, we are done!
        if(  -1 == $i  ) {
            # Reset to starting/sorted order:
            @$vals= reverse @$vals;
            return !1;
        }
        # Re-sort the reversely-sorted tail of the list:
        @{$vals}[$i+1..$last]= reverse @{$vals}[$i+1..$last]
            if  $vals->[$last] < $vals->[$i+1];
        # Find next item that will make us "greater":
        my $j= $i+1;
        $j++
            while   $vals->[$j] <= $vals->[$i];
        do {
            # Swap:
            @{$vals}[$i,$j]= @{$vals}[$j,$i];
            # If "greater" item isn't strictly worse than try it:
            return 1
                if  $Costs[$vals->[$i]] < $Costs[$vals->[$j]]
                ||  $Trims[$vals->[$i]] < $Trims[$vals->[$j]];
            # Else, we picked a strictly worse one, so pick again
            $j++;
        } while(  $j <= $last  );
        # Force us to move back to at least $i-1:
        @{$vals}[$i..$last] = sort { $b <=> $a } @{$vals}[$i..$last];
    }
}

sub cost {
    my( $costs, $trims ) = @_;
    my @order = 0 .. $#$costs;
    my $best = 0;
    my $max = 0;
    do {
        my $size = 1;
        my $cost = 0;
        my $skip = @order;
        for my $i ( @order ) {
            $skip--;
            last
                if  $best  &&  $best < $cost;
            $cost += $size * $costs->[$i];
            $size *= $trims->[$i];
        }
        if(  ! $best  ||  $cost <= $best  ) {
            printf "\r%.3f %.5f ( %s )",
                time() - $Start, $cost, "@order";
            print $/
                if  ! $best;
            @Win = @order;
            $best = $cost;
            $max = 0;
        } elsif(  1 < $skip  ) {
            if(  $max < $skip  ) {
                printf "%4d\b\b\b\b", $skip;
                $max = $skip;
            }
            @order[$#order-$skip+1..$#order] = sort { $b <=> $a }
                @order[$#order-$skip+1..$#order];
        }
    } while(  NextPermuteNum(@order)  );
}