Problem J
Fireworks
The Acme Fireworks Company conducts its shows using a custom-designed firing line with multiple launchers. When multiple shells are fired simultaneously, Acme uses launchers that are spread out as far as possible. For example, when two shells are fired simultaneously, Acme uses the leftmost and rightmost launchers. When three shells are fired, it uses the leftmost launcher, the rightmost launcher, and the launcher that is closest to the center.
Things get complicated as the number of simultaneously fired
shells increases. Acme’s goal is always to make the smallest of
the separations between adjacent launchers as large as
possible. For example, below is one of Acme’s firing lines. The
launchers are labeled
![\includegraphics[width=0.95\textwidth ]{cropped-diagram.pdf}](/problems/utah.fireworks/file/statement/en/img-0001.png)
When three shells are fired, launchers
Now suppose five shells are fired. The optimal smallest
separation of four meters is obtained by using launchers
Input
The first line contains the number
Output
For each scenario, print the optimal smallest separation, followed by a newline.
Sample Input 1 | Sample Output 1 |
---|---|
4 1 1 2 3 3 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
7 3 1 3 5 4 2 2 3 5 6 |
8 4 2 |
Sample Input 3 | Sample Output 3 |
---|---|
12 1 1 1 1 1 1 500000000 1 1 1 1 1 12 |
1 |