Submission #323742

---

Source Code Expand

n = gets.to_i

$c = Array.new(101)
(0..100).each do |i|
	$c[i] = Array.new(101)
	$c[i][0] = $c[i][i] = 1
	(1..(i-1)).each do |j|
		$c[i][j] = $c[i-1][j-1] + $c[i-1][j]
	end
end


$memo = Array.new(101, -1)
def dfs(n)
	return 0.0 if n == 1
	return 1.5 if n == 2
	return $memo[n] if $memo[n] >= 0
	
	p1 = 1.0 / (3 ** (n-1))
	if n % 3 == 0
		p1 += 1.0 * ($c[n][n/3] * $c[n*2/3][n/3]) / (3 ** n)
	end
	
	ret = 0.0
	p2 = 0
	(1..n).each { |v| 
		(v..n).each { |u|
			l = n-v-u
			next if l < 0
			if l == 0
				l = 1000
			end
			next unless (v <= u and u <= l)
			next if (v == u and u == l)
			
			k = (v == u or u == l) ? 3.0 : 6.0
			p2 += k * ($c[n][v] * $c[n-v][u]) / (3 ** n) 
			ret += k * ($c[n][v] * $c[n-v][u]) / (3 ** n) * (1.0 + dfs(v))
		}
	}
	
	$memo[n] = (ret + p1) / (1.0 - p1)
	$memo[n]
end

p dfs(n)

Submission Info

Judge Result