脳log[20110202] Q43, Q44

最終更新: 2011-02-03T09:33+0900

♪ [ProjectEuler] Q43, Q44

 Q43

愚直に。

divisors = [17, 13, 11, 7, 5, 3, 2, 1]
candidates = []
div = divisors.shift
div.step(999, div){|x|
	triplet = [x/100, x/10%10, x%10]
	candidates.push triplet if triplet.uniq!.nil?
}
until divisors.empty?
	div = divisors.shift
	candidates.size.times{
		candidate = candidates.shift
		(0..9).each{|d|
			if ! candidate.include?(d) && 0 == (100*d + 10*candidate[0] + candidate[1]) % div
				candidates.push [d] + candidate
			end
		}
	}
end
candidates.reject!{|c| c[0] == 0 }
p candidates.inject(0){|sum,c| sum + c.join("").to_i }

 Q44

最初に出てきた数字を書いたら通ったけど……。pentagonal numbersの名前の由来もわからんもんね。

_5 = [1] # [P1, P2,...]
_5_index = {1=>0} # 逆引き(Pn=>n-1)辞書
loop{
	i = _5.size
	_5.push(_5.last + 3*i + 1)
	_5_index[_5[i]] = i
	print "."
	(i-1).downto(0){|j|
		diff = _5[i] - _5[j]
		break if diff > _5[j]
		k = _5_index[diff]
		next unless k
		diff2 = _5[j] - _5[k]
		l = _5_index[diff2]
		next unless l
		puts
		puts  "D=#{_5[j]-_5[k]}"
		puts  "#{_5[j]-_5[k]} = P#{j+1}-P#{k+1}"
		puts  "#{_5[l]} = P#{l+1}"
		puts  "#{_5[j]+_5[k]} = P#{j+1}+P#{k+1}"
		print "#{_5[i]} = P#{i+1}"
		gets
	}
}