Problem A. Bullseye
X個目(0 origin)の黒い円の半径 = (r+ 2X + 1)2 – (r+2X)2
a2-b2=(a+b)(a-b)なので上記 = (2r + 4X + 1)
n番目までの円を書くと、使うインクの総量はΣ(x=0 to n) 2r+4x+1
Σ(x=0 to n) x= n(n+1)/2、Σ(x=0 to n) 1=n+1。
ので、上記 = 2n2 + (2r+3)n+(2r+1)となる。
2n2 + (2r+3)n+(2r+1) > t → 2n2 + (2r+3)n+(2r+1) – t > 0
解の公式より上記nを求める
結局perlでやってみた。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
use bignum; my $case = <>; for(my $i=0; $i<$case; $i++){ my @line = split(/ /, <>); my $r = $line[0]; my $t = $line[1]; my $circles = 0; my $n = (sqrt((2*$r+3)**2 - 8 * (2*$r+1-$t))-2*$r-3)/4; $circles = int($n) + 1; # 0 origin print("Case #" . ($i+1) . ": " . $circles . "\n"); } |