# -*- mode: cperl6; -*- # 2011 Perl 6 Coding Contest # Edgar Gonzàlez i Pellicer use v6; use Position; # Target my Int $target; # Best solution so far my Int @best-sol; my Int $best-length; # Find greedy solution sub find-greedy() { # Powers of two up to the target my @powers = 1, 2, 4 ...^ * > $target; # Find bits my @bits = sprintf('%b', $target).comb(/./).reverse>>.Int; # Find first 1 my $i = 0; ++$i while !@bits[$i]; # There will be one for sure # All powers of two will take part in the solution my $sol = @powers; # Find required extra steps my $sum = @powers[$i]; for $i ^..^ +@bits -> $j { if @bits[$j] { $sum += @powers[$j]; $sol.push($sum); } } # Set as solution @best-sol = $sol.list; $best-length = $sol.elems; } # Current solution my Int @current-sol; my Int %current-sol; my Int $current-max; # Backtrack sub backtrack(PosPair $pp0) { # Pruning #1: Larger than the best? return if @current-sol >= $best-length - 1; # Pruning #2: Achivable upper bound is lower than target my $ub = $current-max * (2 ** ($best-length - @current-sol)); return if $ub < $target; # Try with all combinations for $pp0 .. end(@current-sol) -> $pp { # The new one my $new = @current-sol[$pp.i] + @current-sol[$pp.j]; # Larger than the target? if $new > $target { # Skip! } # Is it the target? elsif $new == $target { # We updated the best solution @best-sol = @current-sol; @best-sol.push($new); $best-length = @best-sol.elems; } # Is it not already there? elsif !%current-sol.exists($new) { # Add it %current-sol{$new} = 1; @current-sol.push($new); # Update max my $prev-max = $current-max; $current-max max= $new; # Backtrack from the next position on, # to avoid already tried pairs backtrack($pp.succ); # Restore %current-sol.delete($new); @current-sol.pop(); $current-max = $prev-max; } } } # Solve sub solve(Int $n) { # Positive? if $n > 0 { # Set as target $target = $n; # Find the greedy solution, to allow pruning find-greedy(); # Try to backtrack to improve @current-sol = 1; %current-sol = 1 => 1; $current-max = 1; backtrack(start(@current-sol)); # Show the solution say('(' ~ @best-sol.sort.join(', ') ~ ')'); } else { # Error say('Argument must be positive.'); } } # Main ## Without arguments multi sub MAIN() { # Read and solve each line for $*IN.lines { solve(.Int); } } # Main ## With arguments multi sub MAIN(*@ARGS) { # For each one for @ARGS { solve(.Int); } } # Call main MAIN(|@*ARGS);