Project Euler 85

驚きの適当さ。終了判定すらしていない。なぜかPerl。
最後のほうで出たものが答え。

親の長方形を埋めるための子の長方形の数は、親の長方形の辺の長さが逆転していても同じ。
つまり親の長方形のサイズが3x4でも4x3でも同じだよということ。

パターンの数は力技で数えられる。
親の各辺の長さをxx, yyとし、子候補の各辺の長さをx, yとすると、

( xx - x + 1 ) * ( yy - y + 1 )

個の配置方法があるから、あとは子のサイズ変えて数えるだけ。

#project euler 85

use strict;
use warnings;

my $framex = 3;
my $framey = 2;


my $diff = 9999999;
my $cand_area = 0;
my $target = 2000000;

foreach my $xx ( 1..10000){
	foreach my $yy ( 1..$xx){
		my $fill_patterns = 0;
		foreach my $x ( 1..$xx){
			foreach my $y ( 1..$yy){
				$fill_patterns += ( $xx - $x + 1 ) * ( $yy - $y + 1 );
			}
		}
		if( abs($target - $fill_patterns) < $diff ){
			$diff = abs( $target - $fill_patterns); 
			$cand_area = $xx * $yy;
			print "$diff, $cand_area\r"
		} 
	}
}