STEP 2 is wrong. Try this:

4
100 100 1
100 1 100
1 100 100
50 50 50

The answer should be:
YES
YES
YES
YES!!!

A my idea.
We should find answer for the first contestant.
a[i] b[i] c[i] - is the speeds.
x y z - the lengths.
Write inequation describing that first contestant will win over i-th:
(1/a[1] - 1/a[i])x + (1/b[1] - 1/b[i])y + (1/c[1] - 1/c[i])z < 0
Then, we should answer: are exist such x, y and z, that satisfy this inequations for each i > 1?

Edited by author 30.03.2005 19:31

i find my mistake

program _1084;

{$APPTYPE CONSOLE}

uses
  SysUtils,math;
const
 pi=3.1415926535;
Var
x,l,s,c:real;
begin
  Readln(x,l);
  X:=x/2;
  c:=x*sqrt(2);
  if l>=c then s:=4*x*x;
  if l<=x then s:=pi*l*l;
  if not((l>=c)or(l<=x)) then
   Begin
     s:=8*(x*sqrt(l*l-x*x)/2+l*l/2*(pi/4-arccos(x/l)))
   end;
  writeln(s:0:3);
end.

5
2000
3
4
5
6
The correct answer should be 1988,and what's your answer?

try this test:

5
3 3 2 2 2

the correct answer is 0. your program gives 2.

Edited by author 24.11.2007 02:22

Try to solve problems, witch were solved by a lot of people! Also you can solve problems from school contests (you can find them in contests archive)

I think you've forgotten about the 1st and nth points) And also you should write something like z += ... to count the total direction)
Good Luck!))

Edited by author 24.08.2007 08:57

I had the same problem. But when I replaced "int" with "double", I've got AC. Just try to calculate next expression: 50000*50000 - 50000*(-50000) = ???????????

-1

Edited by author 03.01.2008 14:22

My ansewer -1

use standart input and output stream...

Use scanf instead of cin
Input file is very big >10MB

but better use Pascal:)
I don't optimize input at all. It works about 1.3 sec

After simple optimization 0.328 sec

Edited by author 26.01.2007 16:15

Try to use "gets()" instead "scanf()" and "cin". You can solve it with 2 strings (length = 2*m + 2). I've get AC at 0.156 sec. And some solution are faster.

1
a-b

program ex;

const
  maxn=2000;
  maxm=50;
  zero=1e-15;

var
  g: Array[0..maxn, 1..maxm] of extended;
  cost: Array[1..maxn] of longint;
  from: Array[1..maxn] of longint;
  n, m: longint;
  ans: longint;
  num: Array[1..maxm] of longint;
  tot: longint;
  kk: Array[1..maxn] of longint;

procedure init;
var
  i, j: longint;
begin
  read(n, m);
  for i:=1 to n do
    for j:=1 to m do
      read(g[i, j]);
  for i:=1 to n do begin
    read(cost[i]);
    from[i]:=i;
  end;
end;

procedure qsort(l, r: longint);
var
  i, j: longint;
  x, y: longint;
  t: longint;
begin
  i:=l;
  j:=r;
  x:=cost[(l+r) shr 1];
  y:=from[(l+r) shr 1];
  while i<=j do begin
    while (cost[i]<x)or(cost[i]=x)and(from[i]<y) do inc(i);
    while (cost[j]>x)or(cost[j]=x)and(from[j]>y) do dec(j);
    if i<=j then begin
      g[0]:=g[i];
      g[i]:=g[j];
      g[j]:=g[0];
      t:=cost[i];
      cost[i]:=cost[j];
      cost[j]:=t;
      t:=from[i];
      from[i]:=from[j];
      from[j]:=t;
      inc(i);
      dec(j);
    end;
  end;
  if j>l then qsort(l, j);
  if i<r then qsort(i, t);
end;

function can(x: longint): boolean;
var
  i, j: longint;
  len1, len2: extended;
  sum: extended;
  co: extended;
  tt: extended;
  temp: Array[1..maxn] of extended;
begin
  for i:=1 to tot do begin
    sum:=0;
    len1:=0;
    len2:=0;
    for j:=1 to m do begin
      sum:=sum+g[x, j]*g[i, j];
      len1:=len1+g[x, j]*g[x, j];
      len2:=len2+g[kk[i], j]*g[kk[i], j];
    end;
    len1:=sqrt(len1);
    len2:=sqrt(len2);
    if abs(len1)<=zero then
      exit(false);
    co:=sum/len1/len2;
    tt:=len1*co;
    for j:=1 to m do
      temp[j]:=g[kk[i], j]*tt/len2;
    for j:=1 to m do
      g[x, j]:=g[x, j]-temp[j];
  end;
  for j:=1 to m do
    if abs(g[x, j])>zero then
      exit(true);
  exit(false);
end;

procedure solve;
var
  i: longint;
begin
  qsort(1, n);
  tot:=1;
  num[1]:=from[1];
  ans:=ans+cost[1];
  kk[1]:=1;
  for i:=2 to n do
    if can(i) then begin
      inc(tot);
      kk[tot]:=i;
      num[tot]:=from[i];
      ans:=ans+cost[i];
      if tot=m then
        exit;
    end;
end;

procedure print;
var
  i, j: longint;
  t: longint;
begin
  if tot<m then
    writeln(0)
  else begin
    writeln(ans);
    for i:=1 to m do
      for j:=i+1 to m do
        if num[i]>num[j] then begin
          t:=num[i];
          num[i]:=num[j];
          num[j]:=t;
        end;
    for i:=1 to m do
      writeln(num[i]);
  end;
end;

begin
  init;
  solve;
  print;
end.

can you tell me what the mistake is. coz im also getting WA in test#1 itself

YEAAAAAH, I got AC!!!

I used DP O(n^2)
var
  st : ansistring;
  f : array [0..1010,0..1010] of boolean;
  i,j,cx,cy,max : longint;
begin
  readln(st); max:=0;
  for i:=1 to length(st) do
  for j:=1 to i do f[i,j]:=true;
  for i:=1 to length(st)-1 do
  for j:=1 to length(st)-i do
  if st[j] = st[i+j] then f[j,i+j]:=f[j+1,i+j-1]
                     else f[j,i+j]:=false;

  max:=-1;
  for i:=1 to length(st) do
  for j:=0 to length(st)-i do
  if (f[i,i+j]) and (j>max) then
  begin
    cx:=i;
    cy:=i+j;
    max:=j;
  end;

  for i:=cx to cy do write(st[i]);
  writeln;
end.

>

>