fork download
copy 
  1. #!/usr/bin/perl
  2. use feature qw{:5.16};
  3. my ($hit, $min) = (0, ~0);
  4. sub f {
  5.   local ($_, $m) = @_;
  6.   if (my ($p, $d, $r) = /^(_*)(\d)(.*)$/) {
  7.     $m += length $p;
  8.     return $m if $m > $min; # 枝刈り
  9.     # 目の前の皿をスルーせず数値を食べる
  10.     my $s = "_$r$p";
  11.     my $t = 0; # 食べている間に流れて行ってしまう数値皿の個数
  12.     for (1..$d) { # ローテーション及び食べそびれのカウント
  13.       my $c = substr($s,0,1);
  14.       $t++ if $c =~ /\d/;
  15.       $s = substr($s,1).$c;
  16.     }
  17.     my $m1 = f($s, $m + $d);
  18.     if ($t) { # 食べている間に通り過ぎてしまった数値皿のある場合、
  19.       my $m2 = f("$r$p$d", $m + 1); # 食べずにスルーするケース側の木も計算
  20.       $m1 = $m2 if $m2 < $m1;
  21.     }
  22.     $m = $m1;
  23.   }
  24.   if ($m <= $min) {
  25.     if ($m == $min) { # 最小値は同じだった
  26.       $hit++;
  27.     } else {
  28.       ($hit, $min) = (1, $m);
  29.     }
  30.     say " hit, min = $hit, $min";
  31.     die if $hit >= 20; # 一定以上同じ最小値が繰り返し計算されたら収束と判定し脱出
  32.   }
  33.   $m
  34. }
  35. while (<>) {
  36.   chomp;
  37.   ($hit, $min) = (0, ~0);
  38.   say "\n$_: ";
  39.   eval {f($_, 0)};
  40.   push @a, "$_ : $min\n";
  41. }
  42. print "\n", @a;
Success #stdin #stdout 0s 17632KB
comments (?)
stdin
copy 
3324
stdout
copy 
3324: 
 hit, min = 1, 16
 hit, min = 2, 16
 hit, min = 3, 16
 hit, min = 4, 16
 hit, min = 5, 16
 hit, min = 6, 16
 hit, min = 7, 16
 hit, min = 8, 16
 hit, min = 9, 16
 hit, min = 10, 16
 hit, min = 1, 15
 hit, min = 2, 15
 hit, min = 3, 15
 hit, min = 4, 15
 hit, min = 5, 15
 hit, min = 6, 15
 hit, min = 7, 15
 hit, min = 8, 15
 hit, min = 9, 15
 hit, min = 10, 15
 hit, min = 11, 15
 hit, min = 12, 15
 hit, min = 13, 15

3324 : 15
https://ideone.com/vXrTp8
language:
Perl (perl 5.28.1)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!