## 10382 - Watering Grass

Moderator: Board moderators

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

### 10382 (* stiupid ?? *)

Hello...

i'm trying to solve 10382,
i wrote code but i still getr WA

do u have any intresting tests ?? Regards
MIras

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
You may wanna post in the 103 board.. :p

koala
New poster
Posts: 7
Joined: Sun Mar 28, 2004 9:41 am
Location: Tsinghua University, Peking, P.R.China
Contact:

### 10382 - Watering Grass

My algorithm is:
1. Since covering the entire strip and covering the upper bound are equivalent, each sprinkler can be represented by an interval.
2. Use GREEDY algorithm to solve it.
Is it correct? I think so, but why did I got WA.
[pascal]
Program Watering_Grass;

Const
Maxn=10000;
Zero=1e-3; {I have tried Zero=0 and Zero=1e-6, but both WA}

Type
Intervaltype=Record
x,y:Real;
End;

Var
a:Array [1..Maxn] of Intervaltype;
n,l,w,ans:Longint;

Procedure Input_Data;
Var
i,x,r:Longint;
Begin
For i:=1 to n Do
Begin
If r*r-w*w/4<0
Then Begin a.x:=0; a.y:=0 End
Else Begin
a.x:=x-Sqrt(r*r-w*w/4); a.y:=x+Sqrt(r*r-w*w/4);
End;
End;
End;

Procedure Qsort(p,q:Longint);
Var
r,i,j:Longint;
k:Intervaltype;
Begin
r:=Random(q-p+1)+p;
k:=a[r];
a[r]:=a[p];
i:=p; j:=q;
While i<j Do
Begin
While (i<j) and (k.x<=a[j].x) Do Dec(j);
a:=a[j];
While (i<j) and (a.x<=k.x) Do Inc(i);
a[j]:=a;
End;
a:=k;
If p<i-1 Then Qsort(p,i-1);
If i+1<q Then Qsort(i+1,q);
End;

Procedure Solve;
Var
x,y:Real;
i:Longint;
Begin
Qsort(1,n);
ans:=0;
x:=0;
i:=1;
While (i<=n) and (x<l-zero) Do
Begin
Inc(ans);
y:=x;
While (i<=n) and (a.x<=x+zero) Do
Begin
If a.y>y Then y:=a[i].y;
Inc(i);
End;
If y=x Then Begin ans:=-1; Exit End;
x:=y;
End;
If x<l-zero Then ans:=-1;
End;

Procedure Output_Data;
Begin
Writeln(ans);
End;

Begin
While not EOF Do
Begin
Input_Data;
Solve;
Output_Data;
End;
End.
[/pascal]

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Hi koala,

Haven't look your code, but I suggest you to be careful with precision error. First, I used PASCAL and got WA, but after I translated it to C, I got AC.

Hope it helps,
angga888

shenyute
New poster
Posts: 1
Joined: Tue Jul 27, 2004 2:57 pm

### 10382

angga888 wrote:Hi koala,

Haven't look your code, but I suggest you to be careful with precision error. First, I used PASCAL and got WA, but after I translated it to C, I got AC.

Hope it helps,
angga888
can you give me some sample input to check my code~
i got WA><
thanx~

Yax
New poster
Posts: 1
Joined: Fri Oct 07, 2005 9:18 am

### 10382 TLE

Hello, has anyone some reeeeeal long input to this one? I'm getting TLE and i'm not sure if it is inefficient program or some stupid endless loop inside or slow Java. Thanx.

ZhangChi
New poster
Posts: 4
Joined: Tue Oct 18, 2005 6:55 pm
Contact:
I got WA too....

Is there any trick in the test data ? I need some data.

help!

ZhangChi
New poster
Posts: 4
Joined: Tue Oct 18, 2005 6:55 pm
Contact:
I know the reason now!

there are many blank lines at the end of the test data . so if we use EOF , it can't works well ...... this is my code...

Code: Select all

``````{\$S-,R-}

program UVA10382;

const
maxn	=	10000;

type
tseg	=	record
l , r	:	double;
end;

var
seg	:	array [ 1 .. maxn ] of tseg;
w , l	:	double;
n	:	integer;
tot	:	integer;
ans	:	integer;

procedure init;
var
i	:	integer;
p , r	:	double;
len	:	double;
begin
read ( n , l , w );
tot := 0;
for i := 1 to n do
begin
read ( p , r );
if r * 2 > w then
begin
inc ( tot );
len := sqrt ( sqr ( r ) - sqr ( w / 2 ) );
seg [ tot ] . l := p - len ;
seg [ tot ] . r := p + len ;
end;
end;
end;

function pre ( a , b : tseg ) : boolean;
begin
if a . l < b . l then pre := true else
if a . l > b . l then pre := false else
if a . r > b . r then pre := true else pre := false;
end;

procedure swap ( var a , b : tseg );
var
c	:	tseg;
begin
c := a ; a := b ; b := c;
end;

procedure sort ( h , t : integer );
var
i , j	:	integer;
x	:	tseg;
begin
if h >= t then exit;
i := h ; j := t;
x := seg [ ( h + t ) shr 1 ];
repeat
while pre ( seg [ i ] , x ) do inc ( i );
while pre ( x , seg [ j ] ) do dec ( j );
if i <= j then
begin
swap ( seg [ i ] , seg [ j ] );
inc ( i ) ; dec ( j );
end;
until i > j;
sort ( h , j );
sort ( i , t );
end;

procedure prepare;
var
i , j	:	integer;
begin
n := tot;
tot := 0;
i := 1;
while i <= n do
begin
inc ( tot );
seg [ tot ] := seg [ i ];
j := i + 1;
while ( j <= n ) and ( seg [ j ] . r <= seg [ i ] . r ) do inc ( j );
i := j;
end;
end;

procedure greedy;
var
i , j	:	integer;
x	:	integer;
begin
ans := -1;
if tot = 0 then exit;
if seg [ 1 ] . l > 0 then exit;
if seg [ tot ] . r < l then exit;
i := tot;
while ( i > 1 ) and ( seg [ i ] . l > 0 ) do dec ( i );
x := 1;
while ( i < tot ) and ( seg [ i ] . r < l ) do
begin
j := i + 1;
while ( j <= tot ) and ( seg [ i ] . r >= seg [ j ] . l ) do inc ( j );
dec ( j );
if j = i then exit;
inc ( x );
i := j;
end;
ans := x;
end;

begin
repeat
init;
sort ( 1 , tot );
prepare;
greedy;
writeln ( ans );
while not eof ( input ) and eoln ( input ) do readln;
until eof ( input );
end.``````

kampu
New poster
Posts: 1
Joined: Sun May 21, 2006 1:02 pm
hi! I'm also having TLE and i dont know why, then I need some inputs for prove my code.

Can anybody give us some inputs please?

New poster
Posts: 5
Joined: Tue Sep 20, 2005 2:53 pm
Location: iran
Contact:

### I,ve got WA for (10382) too!

I code this problem in two ways and both of them get WA
my first algorithm is
1.remove all circles which are inside bigger circles.
2.remove all circles which their effecting area(left bound to right bound)
is common with other unremoved circles.
3.count remained circles
i guess its true. but after seeing other posts in this subject i change my algorithm to a simple greedy one that is
1.sort the circles according to the left bound of them
2.from the left cover the grass area with the most rightbound circle which has a less left bound and do this until covering all the area
plz let me know if you find any test case that break the code or one of the algorithm
here is my code
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
struct circle
{
bool mark;
int position;
double left;
double right;
void setRectangle(int ,int);
};
void circle::setRectangle(int w,int l)
{
double temp ;
if(radius > w / 2.0 )
else
{
temp = 0.0;
}
left = position - temp;
if(left < 0.0)
left = 0.0;
right = position + temp;
if(right > l)
right = l;
}
bool operator<(const circle &a, const circle &b)
{
return (a.left < b.left);
}
circle data ;
int main()
{
int n,w,l,counter,index;
double leftBound,rightBound;
bool find ;
while(cin>>n>>l>>w)
{
for(int i=0;i<n;i++)
{
data.setRectangle(w,l);
}
sort(data,data + n);
leftBound = rightBound = 0;
index = counter = 0;
while(leftBound != l)
{
find = false;
for(int i=index;i<n;i++)
{
if(data.left<=leftBound && data.right > rightBound )
{
index = i;
rightBound = data.right;
find = true;
}
}
if(!find)
break;
counter ++;
leftBound = data[index].right;

}
if(find)
cout<<counter<<endl;
else
cout<<-1<<endl;
}
return 0;
}

New poster
Posts: 5
Joined: Tue Sep 20, 2005 2:53 pm
Location: iran
Contact:
is there anybody who can challenge this code?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases.

Input:

Code: Select all

``````11 27 3
1 17
2 18
8 1
6 7
2 3
3 7
12 11
16 16
4 4
12 13
16 18
1 6 26
11 11
15 22 16
3 4
5 13
1 12
18 19
2 15
12 1
11 19
8 10
12 11
7 16
12 2
9 16
6 8
9 6
7 14
11 16 7
2 19
3 10
15 15
5 14
5 7
20 16
4 15
2 7
11 17
1 10
11 19
13 25 9
4 17
19 16
8 11
19 18
6 1
13 12
11 8
11 2
1 11
11 18
20 5
15 14
6 13
11 23 4
15 9
3 10
3 9
17 14
3 20
17 5
13 13
18 14
13 3
17 16
13 18``````
Output:

Code: Select all

``````1
-1
1
1
1
1``````
Hope these help.
Last edited by Jan on Wed Aug 29, 2007 8:39 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

New poster
Posts: 5
Joined: Tue Sep 20, 2005 2:53 pm
Location: iran
Contact:
Now I am getting confused about understanding the problem description!
my output for your test cases is
1
-1
1
1
1
1
and I still can't find out why these 1s should be 2s.
for the first testcase there is the point 16 18 which covers the square completely. for the 3rd and 4th and 5th and 6th testcases I have the same issue with the points 11 19, 2 19, 11 18, 13 18 respectivly.
I know there must be something wrong with my understanding but I can't figure it out
plz help!

Code: Select all

``````
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
struct circle
{
bool mark;
int position;
long double left;
long double right;
void setRectangle(int ,int);
};
void circle::setRectangle(int w,int l)
{
long double temp ;
if(radius > w / 2.0 )
temp = sqrt(((long double)(radius * radius) - (long double)((w * w)/4.0 )));
else
{
temp = 0.0;
}
left = position - temp;
if(left < 0.0)
left = 0.0;
right = position + temp;
if(right > l)
right = l;
}
bool operator<(const circle &a, const circle &b)
{
return (a.left < b.left);
}
circle data ;
int main()
{
int n,w,l,counter,index;
double leftBound,rightBound;
bool find ;
while(cin>>n>>l>>w)
{
for(int i=0;i<n;i++)
{
data[i].setRectangle(w,l);
}
sort(data,data + n);
leftBound = rightBound = 0;
index = counter = 0;
while(leftBound != l)
{
find = false;
for(int i=index;i<n;i++)
{
if(data[i].left<=leftBound && data[i].right > rightBound )
{
index = i;
rightBound = data[i].right;
find = true;
}
}
if(!find)
break;
counter ++;
leftBound = data[index].right;

}
if(find)
cout<<counter<<endl;
else
cout<<-1<<endl;
}
return 0;
}
``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I was checking some random cases with my old(WA) code. However, I have taken the correct code and ran both the codes, the outputs are equal. I have checked some hand made cases, too. I m still trying. However, if you want the accepted code then PM me.
Ami ekhono shopno dekhi...
HomePage

Terro
New poster
Posts: 4
Joined: Sat Sep 01, 2007 3:21 pm

### why runtime error?

A strange problem:
My program can run well when inputting the sample data and the data from Jan. But when I submit, I got a Runtime Error:

Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference

Here is my program:

Code: Select all

``````#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

struct node
{
double begin, end;
} section;

inline int cmp(const void* a, const void* b)
{
return ((node*)a)->begin > ((node*)b)->begin ? 1 : -1;
}

int main()
{
int n, l, w, r, pos;
while (cin >> n)
{
cin >> l >> w;
double w2 = double(w*w)/4;
for (int i = 1; i <= n; i++)
{
cin >> pos >> r;
double tmp = sqrt(r*r-w2>0 ? r*r-w2 : 0);
section[i].begin = pos - tmp;
section[i].end = pos + tmp;
}
qsort(&section, n, sizeof(node), cmp);
double st = 0;
int count = 0, p = 0;
if (section.begin > 0 || n <= 0 || w <= 0 || l <= 0)
{
cout << "-1\n";
st = l;
count = -1;
}
while (st < l)
{
double tmpmax = 0;
int maxi = p;
while (section[++p].begin <= st)
if (section[p].end - st > tmpmax)
{
tmpmax = section[p].end - st;
maxi = p;
}
if (maxi == p)
{
cout << "-1\n";
st = l;
count = -1;
}
else
{
st = section[maxi].end;
count++;
}
}
if (count > 0)
cout << count << endl;
}
return 0;
}
``````