Calculate minimum choco.

choco2.pl

#!usr/bin/perl

use strict;
use warnings;
use utf8;

use Math::BigInt lib => 'GMP';

binmode STDOUT, ":utf8";

# 問題の数

my $expect = Math::BigInt->new('280671392065546467397265294532969672241810318954163887187279320454220348884327');

# 素因数分解で得られた素因数

my @primes = map { Math::BigInt->new( $_ ); }
    split( 'x', '358456949x369941863x369941863x162425297x215940091x706170617x479871607x481362815814826159' );

# 素因数をかけて元の数が得られるかどうかを念のため確認

my $result = Math::BigInt->new('1');

for my $prime ( @primes ) {
    $result->bmul( $prime );
}

print "EXPECTED  : $expect\n";
print "CALCULATED: $result\n";
if ( $expect == $result ) {
    print "OK!\n";
} else {
    print "NG!\n";

    exit 1;
}

# しらみつぶしに最小になるパターンを探す

my $num_primes = scalar(@primes);

# 素因数を縦、横、高さのいずれかに使うことになるので、重複を含めると
# 「3^素因数の数」だけパターンがある

my $patterns = 3 ** $num_primes;
print "$patterns patterns.\n";
my ( $minimum_choco, $minimum_choco_factors );

for my $i ( 0 .. $patterns - 1 ) {
    my @factors = map { Math::BigInt->new( $_ ); } ( '1', '1', '1' );

    # 3進数の1桁1桁が、それぞれの素因数を縦、横、高さのいずれに使うかを
    # あらわしている

    for my $j ( 0 .. $num_primes - 1 ) {
        my $c = int( $i / ( 3 ** $j ) ) % 3;
        # print "$c\n";print ref $factors[$c], ", ", ref $primes[$j], "\n";
        $factors[$c]->bmul( $primes[$j] );
    }

    # 縦 <= 横 <= 高さになるように並び替え

    @factors = sort @factors;

    my $choco = calc_choco( @factors );
    my $factors_str = join 'x', @factors;
    # print "$factors_str ($choco)\n";

    # 見つかったパターンがこれまでで最小ならば更新する

    if ( !defined $minimum_choco || $minimum_choco > $choco ) {
        $minimum_choco = $choco;
        $minimum_choco_factors = $factors_str;
    }
}

# 得られた最小のパターンを表示

print "$minimum_choco_factors\n";
print " ($minimum_choco)\n";

# 長方形の表面積 ( = チョコを塗る量) を計算する

sub calc_choco {
    my @dwh = @_;

    return ( $dwh[0] * $dwh[1] + $dwh[1] * $dwh[2] + $dwh[2] * $dwh[0] ) * 2;
}

exit 0;

1;