My solution uses binary search to find such height for second lamp that garland is never under the floor and this height is the lowest possible. For checking that garland is never under the floor I use simple O(N).

I have used a simulation method, first I have built that garland thinking that second lamp is at the same height as first, then Ive calculated then minimum of i*H[i] and lowered the garland by the result, and the resulted height of Nth lamp was the answer. Overall O(n) I think.

I like the idea of binary search, but I check that garland is never under the floor in O(1).
    It easily can be proved, that the garland has an equation x*x+p*x+A. p is a parameter of binary search. Also it's known, that such a parabola(defined in integer points only) has minimum in floor(0.5-p/2). So the checking is very easy.

Edited by author 27.07.2004 14:40

Knowing that the form of the garland is parabola and knowing exact solution for h[i], it is very easy to check minimal B:
 n--;
 for(i=1;i<n;i++)
   if((tmp=(n-i)*(n*i-a)/i) >b) b = tmp;
That's all! b is answer!

It is short. But while you will think about a garland's form, I will have written a solution, based on binary search. In real competition it is better.

Actually,we can get the formula by mathematical induction very easily.We can see:
h1=h1,
h2=h2,
Since hn+1=2hn-h(n-1)+2,
so we can find:
h3=2h2-h1+2,
h4=3h2-2h1+6,
h5=4h2-3h1+12,
and by mathematical induction,not difficult to prove:
hn=(n-1)h2-(n-2)h1+n(n+1).
Thus we can trace every hi>0 and get the minimum for h2 and then we can find hn.

Guys why this cleverness. Binary search - is solution that author recognized I think. But about parabolf thinking is good idea - you're clever boys ;)

I have change h2 to h, h1 to A and n to x. Then i have get something like x^2+bx+c. hn>0 if that formula ax^2+bx+c>=0. Its possible only if D<=0. I have found and get the othe formula but now with h like h^2+bh+c.
After that i have found h1 and h2, and choose the smallest bigger than 0. And that result i have written in the first formula, and have found B. But the problem that my result is different from the real, but not very much.
its my code:

#include <stdio.h>
#include <math.h>

int main()
{
    int N,i;
    double h1,h2,A,B,min;
    scanf("%d%lf",&N,&A);
    h1=A+1.0+2*sqrt(A);
    h2=A+1.0-2*sqrt(A);;
    if(h2<h1&&h2>0) min=h2;
    else min=h1;
    B=(N-1)*min-(N-2)*A+(N-1)*(N-2);
    printf("%0.2lf",B);
    return 0;
}

PS sorry for my English

Edited by author 27.06.2008 02:38

a2=(1/2)a1 + (1/2)a3 -1
a3=(1/3)a1 + (2/3)a4 -2
a4=(1/4)a1 + (3/4)a5 -3
...
an=(1/n)a1 + ((n-1)/n) a(n+1) - (n-1)

Just by putting a2 into a3's initial formula a3=(1/2)(a2+a4) -1 and so on, you can get the relationship of an and a(n+1), then you can guess An, and calculate the whole sequence. As long as ai>=0, An can be lower, in this way you'll get the answer.