999 987.23
answer 934270.79

3 100
answer 0.00

4 1000
answer 0.00

5 12
answer 0.00

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).

And,here it is:

program wx;
  var i,j,k,m,n:longint;
      b,c,s,t:extended;
  begin
    readln(n,c);
    dec(n);
    m:=trunc(sqrt(c));
    if m>=n then
      begin
        writeln('0.00');
        exit;
      end;
    if c/m<=m+1 then
      begin
        b:=m+c/m;
        s:=n*n-b*n+c;
      end
    else s:=1e100;
    inc(m);
    if c/m>=m-1 then
      begin
        b:=m+c/m;
        t:=n*n-b*n+c;
      end
    else t:=1e100;
    if s<t then writeln(s:0:2)
      else writeln(t:0:2);
  end.

#include<iostream.h>
#include<math.h>
int ji(int n);
int main()
{
    int k,n,m,c,a;
    int d=0;
    cin>>n>>k;
    if((k>=2&&k<=10)&&n>=2&&(n+k)<=18)
    {
        m=0;
        if(n%2==1)
        while(m<(n+1)/2)
        {
            c=ji(n-m);
            a=ji(m);
            d=d+int(pow(k-1,n-m-1)*c/a/ji(n-m-m));
            m++;
        }
        else
        while(m<=(n+1)/2)
        {
            c=ji(n-m);
            a=ji(m);
            d=d+int(pow(k-1,n-m-1)*c/a/ji(n-m-m));
            m++;
        }
        cout<<(k-1)*d<<endl;
    }
    return 0;
}

int ji(int n)
{
    if(n==0)
        return 1;
    else
        return n*ji(n-1);
}

H(i+1)-H(i)=H(i)-H(i-1)+2;

denote d(i)=H(i+1)-H(i)

you can get: d(i)=d(i-1)+2;

H(N)-H(1)=(N-1)d(1)+(N-1)(N-2);

H(i)-H(1)=(N-1)d(i)+(i-1)(i-2);

according to the above two equation, denote H(i)=0

you will get:H(N)=(N-i)*((N-1)-H1/(i-1));

the maximun of H(N) is the answer .so strange!

Edited by author 08.03.2009 15:00

Edited by author 08.03.2009 15:00

After I get the function f(N)= N*N+a*N+(A-a-1), I solve f(a/2)=0 getting value of a, after that I find the two integar s1 s2 nearest to a and let f(s1) = 0 || f(s2) = 0 to min this function. An exception is a/2 > the N given by this problem, in this case it should be 0

please send me the solution of this question

muhamed@netmail.kg

It says that "no lamp in the garland lies on the ground ", it means that h[i] and h[i+1] can't be both 0 at the same time. if my program considers it ,it got WA on #5,but it got AC when i ignore it.

I have seen a AC program which doesn't care about the condition.

Am i wrong?

Can anyone just explain in slight detail about how binary search can be used to solve this problem.

There is a small trick at this problem.
Whoever gets WA, should try this test:

30 1000

The right answer is 0.00

#include <stdio.h>
#define eps 0.00000001

double A, B=((1<<31)-1), DMin=((1<<31)-1);
int N;

void bs()
{
        double p1 = A, p2 = 0, mij, a1, a2, a3, min;
        int i;

        while ((p1-p2)>eps)
        {
                min = A;
                mij  = (p1+p2)/2;
                a1 = A; a2 = mij;
                for (i = 2; i < N; i++)
                {
                        a3 = 2*(a2+1)-a1;
                        a1 = a2;
                        a2 = a3;
                        if (a3 < 0)
                        {
                                p2 = mij+eps;
                                break;
                        }
                        else
                            if (min > a3) min = a3;
                }
                if (i == N)
                {
                   if ((B-a3)<eps) p2=2*p1;
                   if ((DMin-min) > eps) DMin = min, B = a3;
                   p1 = mij-eps;
                }
        }
}

int main()
{
        scanf("%d %lf", &N, &A);
        bs();
        printf("%.2lf\n", B);

        return 0;

}

English:

It's said that H[i]=(H[i-1]+H[i+1])/2, but we know only height of first lamp, so when we try to determine height of second lamp, where from do we take H[3] ??? Don't I unterstand question right ???
  Please explain me, if you can.



Exactly same text in Russian:

Сказано, что H[i]=(H[i-1]+H[i+1])/2, но мы знаем только высоту первой лампочки, а когда мы определяем высоту второй лампочки откуда брать высоту третей H[3] ??? Или я не совсем правильно понял вопрос ???
  Объясните кто-нибудь, пожалуйста.

Edited by author 18.01.2006 18:04

This is my code:

{$N+}
program u1066;

 var
   n,i:longint;
   a1,an,tmp:extended;

begin
  readln(n,a1);
  for i:=3 to n do
  begin
    tmp:=(a1-i+1)*(i-2)/(i-1);
    if tmp>an then an:=tmp;
  end;
  an:=(n-1)*an+(n-1)*(n-2)-(n-2)*a1;
  if an<0 then an:=0;
  writeln(an:0:2);
end.

I tried these:
100 100 =>7921.00
10 11 =>32.00
123 456 =>10128.86
111 111 =>9891.00
8 15 =>9.75
5 10 =>0.67
70 50 =>3835.14
1000 1=>996004.00

.

I've tried every tests i could found.
It's all right.
But i keep getting WA.
This is my program:

var t,n,l:integer;
    a:real;
    sz:array[1..1000]of record
                              x:integer;
                              n:real;
                        end;
    x,min,k:real;
    q:boolean;
begin
     readln(n,a);
     fillchar(sz,sizeof(sz),0);
     sz[1].n:=a;
     sz[2].x:=1;
     for t:=3 to n do
         begin
              sz[t].x:=sz[t-1].x*2-sz[t-2].x;
              sz[t].n:=(sz[t-1].n+1)*2-sz[t-2].n;
         end;
     min:=-1;
     for t:=2 to n-1 do
         begin
              x:=(-sz[t].n)/sz[t].x;
              q:=true;
              for l:=2 to n do
                  begin
                       k:=sz[l].x*x+sz[l].n;
                       q:=q and(k>=0);
                  end;
              k:=sz[n].x*x+sz[n].n;
              if ((k<min)or(min=-1))and(q) then
                 min:=k;
         end;
     writeln(min:0:2);
end.

program ural1066;
var
  n,i:integer;
  a,b,c,l,r,h2:real;
  h1:real;
begin
  readln(n,h1);
  l:=0;r:=maxlongint;
  repeat
    b:=h1;
    h2:=(l+r)/2;c:=h2;
    for i:=3 to n do begin
      a:=b;b:=c;c:=2*(b+1)-a;
      if c<0 then break;
    end;
    if c<0 then l:=h2 else r:=h2;
  until r-l<1e-4;
  writeln(abs(c):0:2);
end.

    Help!I use binary search to find the answer.
Please give me some test! Thanks
{my wrong mode here}
const
  maxn=1000;
  maxm=1000000;
var
  a1,n:longint;
  ta1:real;
  a:array[1..maxn]of extended;

  procedure init;
  begin
{    assign(input,'1066.in'); reset(input);}
    readln(n,ta1);
    a1:=round(ta1*maxm);
    a[1]:=a1;
  end;

  procedure search(first,last:longint);
  var
    cha1,cha2:real;
    h,h1,h2:longint;

  function solve(x:longint):boolean;
  var
    te,i,j:longint;
  begin
    i:=2; a[2]:=x; solve:=true;
    repeat
      inc(i);
      a[i]:=2*(a[i-1]+maxm)-a[i-2];
      if a[i]<0
        then begin
          solve:=false; exit;
        end;
    until a[i]>a[i-1];
    dec(I);
    if first=last
      then begin
        for j:=i+1 to n do
          a[j]:=2*(a[j-1]+maxm)-a[j-2];
        writeln((a[n]/maxm):0:2);
        halt;
      end;
  end;

  begin
    h:=(first+last) div 2;
    if solve(h)
      then search(first,h)
      else search(h+1,last);
  end;

begin
  init;
  search(0,a1);
end.

if the input is 5 10,whats the answer?
if there is no solutions to the input,how to do with it?

#include<stdio.h>
//Who can tell me why my programme is wrong? It seem to be so
//simple and I think is should be right.
#define Max(a,b) (a>b?a:b)

typedef long double type;

double N;
type H1,H2;

int main()
{ float a;
  type i;
 scanf("%lf %f",&N,&a); H1=(type)a; H2=0;
 for (i=2; i<=N; i++) H2=Max(H2,(H1*(i-2)-(i-1)*(i-2))/(i-1));
 printf("%0.2lf\n",(double)Max(0,H2*(N-1)-H1*(N-2)+(N-1)*(N-2)));
 return 0;
}