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 >= 10; # 一定以上同じ最小値が繰り返し計算されたら収束と判定し脱出
  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 0.04s 17632KB
comments (?)
stdin
copy 
12_3
313__
4_35_1264_23_434
123456789123456789
88967472612377988186
19898693316679441672
93769682716711132249893
stdout
copy 
12_3: 
 hit, min = 1, 6
 hit, min = 2, 6
 hit, min = 3, 6
 hit, min = 4, 6

313__: 
 hit, min = 1, 10
 hit, min = 2, 10
 hit, min = 3, 10
 hit, min = 1, 8
 hit, min = 2, 8
 hit, min = 3, 8
 hit, min = 4, 8
 hit, min = 5, 8

4_35_1264_23_434: 
 hit, min = 1, 62
 hit, min = 2, 62
 hit, min = 3, 62
 hit, min = 1, 60
 hit, min = 2, 60
 hit, min = 3, 60
 hit, min = 4, 60
 hit, min = 5, 60
 hit, min = 6, 60
 hit, min = 7, 60
 hit, min = 8, 60
 hit, min = 9, 60
 hit, min = 10, 60

123456789123456789: 
 hit, min = 1, 98
 hit, min = 2, 98
 hit, min = 3, 98
 hit, min = 4, 98
 hit, min = 5, 98
 hit, min = 6, 98
 hit, min = 7, 98
 hit, min = 8, 98
 hit, min = 9, 98
 hit, min = 10, 98

88967472612377988186: 
 hit, min = 1, 151
 hit, min = 2, 151
 hit, min = 3, 151
 hit, min = 1, 149
 hit, min = 2, 149
 hit, min = 3, 149
 hit, min = 4, 149
 hit, min = 5, 149
 hit, min = 6, 149
 hit, min = 7, 149
 hit, min = 8, 149
 hit, min = 9, 149
 hit, min = 10, 149

19898693316679441672: 
 hit, min = 1, 170
 hit, min = 2, 170
 hit, min = 3, 170
 hit, min = 4, 170
 hit, min = 5, 170
 hit, min = 6, 170
 hit, min = 7, 170
 hit, min = 8, 170
 hit, min = 9, 170
 hit, min = 10, 170

93769682716711132249893: 
 hit, min = 1, 176
 hit, min = 2, 176
 hit, min = 1, 170
 hit, min = 2, 170
 hit, min = 3, 170
 hit, min = 4, 170
 hit, min = 5, 170
 hit, min = 6, 170
 hit, min = 7, 170
 hit, min = 8, 170
 hit, min = 9, 170
 hit, min = 10, 170

12_3 : 6
313__ : 8
4_35_1264_23_434 : 60
123456789123456789 : 98
88967472612377988186 : 149
19898693316679441672 : 170
93769682716711132249893 : 170
https://ideone.com/0yJ5U9
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!