-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem_61.pl
executable file
·105 lines (89 loc) · 2.04 KB
/
problem_61.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#!/usr/bin/perl
use strict;
use warnings;
use feature qw(say);
sub gen_seq {
my $func = shift;
my $m = shift;
my $n = shift;
my $res = {};
my $i = 0;
while (++$i) {
my $x = $func->($i);
last if ($x >= $n);
if ($x >= $m) {
$x =~ /(\d\d)(\d\d)/;
push @{$res->{$1}}, $2;
}
}
return $res;
}
my @seq;
push @seq, gen_seq(sub {
my $n = shift; return $n * ($n + 1) / 2;
}, 1000, 10000);
push @seq, gen_seq(sub {
my $n = shift; return $n * $n;
}, 1000, 10000);
push @seq, gen_seq(sub {
my $n = shift; return $n * (3 *$n - 1) / 2;
}, 1000, 10000);
push @seq, gen_seq(sub {
my $n = shift; return $n * (2 * $n - 1);
}, 1000, 10000);
push @seq, gen_seq(sub {
my $n = shift; return $n * (5 *$n - 3) / 2;
}, 1000, 10000);
push @seq, gen_seq(sub {
my $n = shift; return $n * (3 *$n - 2);
}, 1000, 10000);
my %g = ();
for (my $i = 0; $i < @seq; $i++) {
for (my $j = 0; $j < @seq; $j++) {
next if $i == $j;
my %s1 = %{$seq[$i]};
my %s2 = %{$seq[$j]};
foreach my $k (keys %s1) {
foreach my $v (@{$s1{$k}}) {
push @{$g{$k}}, [$j, $v] if exists $s2{$v};
}
}
}
}
sub find_chain {
my $n = shift;
my $v = shift;
my $prev = shift;
my @stack = @_;
if( @stack == @seq ) {
if ( $stack[0][0] == $n &&
$stack[0][1] == $v
) {
$stack[0][2] = $prev;
return @stack;
} else {
return ();
}
}
my @n = map {$_->[0];} @stack;
if( $n ~~ @n ) {
return ();
}
push @stack, [$n, $v, $prev];
my @allow = grep { $_->[1] ~~ $seq[$n]->{$v} } @{$g{$v}};
foreach (@allow) {
my @s = find_chain($_->[0], $_->[1], $v, @stack);
return @s if @s;
}
return ();
}
my @s;
foreach (keys %{$seq[0]}) {
@s = find_chain(0, $_, 'x', ());
last if @s;
}
my $sum = 0;
foreach (@s) {
$sum += $_->[2] . $_->[1];
}
say $sum;