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
|
#!/usr/bin/env perl
use strict;
use warnings;
### HELPER
# Find all divisors of $n
sub get_divisors {
my($number, @fdiv, @sdiv) = (shift);
if ($number > 3) {
foreach (2..sqrt $number) {
if ($number % $_ == 0) {
push @sdiv, $number / $_;
push @fdiv, $_ if ($number / $_ != $_);
}
}
}
(1, @fdiv, reverse @sdiv)
}
### MAIN
sub is_weird {
my(@track, @subset) = ();
my($number, $sum) = (shift, 0);
my @divisors = get_divisors $number;
$sum += $_ foreach (@divisors);
if ($sum > $number) {
my $now = 0;
LOOP: {
foreach (@divisors) {
if ($now + $_ == $number) {
$now += $_;
push @subset, $_;
last;
} elsif ($now + $_ < $number) {
$now += $_;
push @subset, $_;
push @track, $_;
} else {
# Backtracking
$now = $_;
@subset = ($_);
foreach (reverse @track) {
if ($now + $_ < $number) {
$now += $_;
push @subset, $_;
} elsif ($now + $_ == $number) {
$now += $_;
push @subset, $_;
last LOOP;
}
}
@track = ($_);
}
}
}
if ($now == $number) {
print "Output: 1\n";
print "proper divisors: @divisors\n";
print "subset: @subset => sum = $number\n";
} else {
print "Output: 0\n";
print "proper divisors: @divisors\n";
print "No subset of these sums to $number\n";
}
} else {
print "Output: 1\n";
print "Total sum of the divisors = $sum < $number\n";
}
}
print "Input: ";
my $input = <STDIN>;
is_weird $input;
|
