use strict;
use warnings;

sub greedy_change {  
    my $change = shift;
    my @coins  = @_;

    my @result;
    for my $i (0..$#coins) {
       my $val = int($change/$coins[$i]);
       $change -= $val*$coins[$i];
       push @result,$val;
    }
    return @result;
}
                                                                                                                                                                                                                                                
sub pearson_counterexample {
   my $i = shift;
   my $j = shift;
   my @coins  = @_;
                                                                                                                        
   # Let position $i be the highest coin used,
   # Let positon $j be the lowest.  Then the
   # potential counterexample will be:
   #   1) Compute the greedy change for the
   #      next highest coins value - 1.
   #
   #   2) Copy all coin counts from 0 to $j-1
   #
   #   3) Add one to the coin count at position $j.
   #
   # If this combination is more efficient than
   # the greedy value, we have a counterexample.
                                                                                                                        
   my $value = $coins[$i-1] - 1;
   my @greedy = greedy_change($value, @coins);
   my @example = (0) x @coins;
   $example[$_] = $greedy[$_] for (0..$j-1);
   $example[$j] = $greedy[$j]+1;
                                                                                                                        
   # Compute the numeric value and see if it
   # represents the amount more efficiently
   # than the greedy way.
   my $example_value = 0;
   $example_value += $coins[$_]*$example[$_] for (0..$#example);
   @greedy = greedy_change($example_value, @coins);
   my ($example_count, $greedy_count);
   $example_count += $example[$_] for (0..$#example);
   $greedy_count += $greedy[$_] for (0..$#greedy);
                                                                                                                        
   # This candidate case did not work.
   return if $example_count >= $greedy_count;
   return @example;
}
                                                                                                                        
# Read the coin system from the command line, in
# decreasing order of size.
my @coins = @ARGV;
if (@coins < 3) {
   print "Must have a least three coins\n";
   exit(1);
}
my ($i,$j);
my $found = 0;
                                                                                                                        
EXAMPLES:
for ($i = 1; $i < @coins; ++$i) {
  for ($j = $i; $j < @coins; ++$j) {
    my @example = pearson_counterexample($i, $j, @coins);
    if (@example) {
       print "Counterexample: ",join(" ",@example),"\n";
       $found = 1;
       last EXAMPLES;
    }
  }
}
                                                                                                                        
print "No counterexamples found.  Good coin system\n" unless $found;