Instantly share code, notes, and snippets.

Embed
What would you like to do?
Calculate minimum choco.
#!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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment