Angry Cows
골드 II의견: 0
Bessie the cow has designed what she thinks will be the next big hit video game:
"Angry Cows". The premise, which she believes is completely original, is that
the player shoots a cow with a slingshot into a one-dimensional scene
consisting of a set of hay bales located at various points on a number line; the
cow lands with sufficient force to detonate the hay bales in close proximity to
her landing site, which in turn might set of a chain reaction that causes
additional hay bales to explode. The goal is to use a single cow to start a
chain reaction that detonates all the hay bales.
There are \(N\) hay bales located at distinct integer positions
\(x_1, x_2, \ldots, x_N\) on the number line. If a cow is launched with power \(R\)
landing at position \(x\), this will causes a blast of "radius \(R\)", engulfing all
hay bales within the range \(x-R \ldots x+R\). These hay bales then themselves
explode (all simultaneously), each with a blast radius of \(R-1\). Any
not-yet-exploded bales caught in these blasts then all explode (all
simultaneously) with blast radius \(R-2\), and so on.
Please determine the minimum amount of power \(R\) with which a single cow may be
launched so that, if it lands at an appropriate location, it will cause
subsequent detonation of every single hay bale in the scene.
Problem credits: Brian Dean
Problem credits: Brian Dean
The first line of input contains \(N\) (\(2 \leq N \leq 50,000\)). The remaining
\(N\) lines all contain integers \(x_1 \ldots x_N\) (each in the range
\(0 \ldots 1,000,000,000\)).
Please output the minimum power \(R\) with which a cow must be launched in order
to detonate all the hay bales. Answers should be rounded and printed to exactly
1 decimal point.
angry.inangry.out5
8
10
3
11
13.0In this example, a cow launched with power 3 at, say, location 5, will cause
immediate detonation of hay bales at positions 3 and 8. These then explode
(simultaneously) each with blast radius 2, engulfing bales at positions 1 and
10, which next explode (simultaneously) with blast radius 1, engulfing the final
bale at position 11, which finally explodes with blast radius 0.
평가 및 의견
Angry Cows
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Angry Cows