Google Code Jam Round 1A – Problem A. Bullseye

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でやってみた。

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");
}

コメントを残す