10382 - Watering Grass

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Sep 01, 2007 4:37 pm

I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case

Input:

Code: Select all

12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2
Output:

Code: Select all

-1
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

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

Post by Terro » Sat Sep 01, 2007 5:16 pm

Jan wrote:I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case

Input:

Code: Select all

12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2
Output:

Code: Select all

-1
Hope it helps.
Thanks a lot.
I've modified my program. And I didn't get RE. But after modifying, I got WA. Here is my new program

Code: Select all

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

struct node
{
	double begin, end;
} section[10001];

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[1], n, sizeof(node), cmp);
		double st = 0;
		int count = 0, p = 0;
		if (section[1].begin > 0 || n <= 0 || w <= 0 || l <= 0)
		{
			cout << "-1\n";
			st = l;
			count = -1;
		}
		while (st < l)
		{
			double tmpmax = 0;
			int maxi = p;
			int pre = maxi;	//In order to check wheather it's able to find the next section
			while (section[++p].begin - st < 1e-8 && p <= n)
				if (section[p].end - st > tmpmax)
				{
					tmpmax = section[p].end - st;
					maxi = p;
				}
			if (maxi == pre)
			{
				cout << "-1\n";
				st = l;
				count = -1;
			}
			else
			{
				st = section[maxi].end;
				count++;
			}
		}
		if (count > 0)
			cout << count << endl;
	}
	return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Sep 01, 2007 5:30 pm

Try the cases.

Input:

Code: Select all

2 26 6
4 10
16 14
10 6 37
20 4
19 20
19 2
8 4
7 19
7 14
3 17
1 19
18 1
15 19
Output:

Code: Select all

2
2
Hope these help.
Ami ekhono shopno dekhi...
HomePage

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

Post by Terro » Sun Sep 02, 2007 10:29 am

Jan wrote:Try the cases.

Input:

Code: Select all

2 26 6
4 10
16 14
10 6 37
20 4
19 20
19 2
8 4
7 19
7 14
3 17
1 19
18 1
15 19
Output:

Code: Select all

2
2
Hope these help.
Really thanks for your datas. It just helped me find a mistake. But I still get WA. I've been very confused. Could you please give me some advice? Thanks a lot.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Sep 02, 2007 7:26 pm

Check the following files...

Input
Ouput
Hope these help.
Ami ekhono shopno dekhi...
HomePage

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

Post by Tirdad » Mon Sep 03, 2007 5:45 am

Jan said:
I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case

Input:
Code:
12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2

Output:
Code:
-1
I checked this test case too and it produced the correct output with my binary. now I guess that there might be some coflicts with the compilers.
I use VS2005 but in near future I switch to a better substitude!
can you tell me what is your IDE and compiler Jan?
by the way I cheched the input and output file that you upload and unfortunatly the code is still correct!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Sep 03, 2007 6:43 am

My compiler is MS visual studio 6.0. Its hard to generate effective cases for geometry problems. The random cases matched! Thats why I had to check your coe manually. But couldnt figure out the error.
Ami ekhono shopno dekhi...
HomePage

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

Post by Terro » Mon Sep 03, 2007 3:23 pm

Jan wrote:Check the following files...

Input
Ouput
Hope these help.
I've been really confused. I checked my program using these datas just now. It worked well. But I still got a WA.
So what should I exactly do?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Sep 05, 2007 7:51 am

There can be precision errors. For floating point numbers you should use the comparisons as follows:

Code: Select all

 int	   double
a == b	fabs(a-b) < eps
a != b	fabs(a-b) > eps
a > b	 a > b + eps
a < b	 a + eps < b
Here 'eps' is a small value. Its better to set 'eps' from 10^(-7) to 10^(-11). Hope it works.
Ami ekhono shopno dekhi...
HomePage

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 10382 - Watering Grass

Post by Leonid » Tue Nov 18, 2008 6:53 pm

I'm reaaaaaly confused why I can get AC for this task.
1. I've passed sample cases
2. I've passed all test cases on the board
3. I've passed around 4000 randomly generated test cases verified with http://www.uvatoolkit.com
4. I've found that the problem contains such values with l == 0 or w == 0 and I suspect that the answer for the test cases snould be 0, while the answers produced by http://www.uvatoolkit.com does not follow this logic.
5. I've tried to change EPS value to 1e-7, 1e-11, 1e-13 but still WA
6. WHAT A F*** HAVE I MISSED OUT? When I look at the code I don't feel that there are many mistakes to do so I'm asking for your help guys, please find my mistake!

Code: Select all

const double EPS = 1e-11;
typedef pair<double, double> pii;
bool solve() {
	int n, l, w;
	if (scanf("%d %d %d ",&n,&l,&w) != 3)
		return false;

	vector<pii> sprinklers;
	for (int i = 0; i < n; i++) {
		int p, r;
		scanf("%d %d ",&p,&r);
		pii pd;
		if (2 * r > w) {
			double d = sqrt(r * r - (w * w) / 4.0);
			pd.first = p - d;
			pd.second = p + d;
			sprinklers.push_back(pd);
		}
	}
	sort(sprinklers.begin(), sprinklers.end());
	int m = SZ(sprinklers);
	
	double start = 0;
	int j = 0, total = 0, pj = 0;
	while (start < (double)l - EPS) {
		double go = start;
		while (j < m && sprinklers[j].first - EPS < start) {
			go = max(go, sprinklers[j].second);
			j++;
		}
		if (pj == j) {
			printf("-1\n");
			return true;
		}
		pj = j;
		start = go;
		total++;
	}
	printf("%d\n", total);

	return true;
}

Sanik
New poster
Posts: 1
Joined: Wed Sep 16, 2009 4:33 am

Re: 10382 - Watering Grass

Post by Sanik » Wed Sep 16, 2009 4:42 am

For those who have got an WA, this may be the problem you are facing,
I've finally found why I couldn't get an AC after testing all the test cases others have posted(which were all correct).
But I still can't figure out why it is caused ....

At somewhere in my code I wrote

Code: Select all

double length_2 = sqrt((double)(rad*rad)-w2_2);
and got a WA

But when I changed it to

Code: Select all

double length_2 = sqrt((double)rad*rad-w2_2);
I got an AC

But to my knowledge it should be the same(even safer to give a bracket)

Can anybody tell me why??
-------
I've found out why....because it may overflow.... if I used (double)rad*rad

ACslow
New poster
Posts: 1
Joined: Tue Apr 05, 2011 4:23 pm

10382-watering grass

Post by ACslow » Tue Apr 05, 2011 4:30 pm

Code: Select all

var p,pi,t,len,n,w,i,tot:longint;
    l,r:array[0..10000]of double;
    now,max:double;
    flag:boolean;
procedure qsort(x,y:longint);
  var i,j:longint;
      k,temp:double;
  begin
    i:=x;j:=y;k:=l[(i+j) div 2];
    repeat
      while l[i]<k do inc(i);
      while l[j]>k do dec(j);
      if not (i>j) then begin
        temp:=l[i];l[i]:=l[j];l[j]:=temp;
        temp:=r[i];r[i]:=r[j];r[j]:=temp;
        inc(i);dec(j);
      end;
    until i>j;
    if x<j then qsort(x,j);
    if i<y then qsort(i,y);
  end;

begin
  while not eof do begin
    readln(n,len,w);
    t:=0;
    for i:=1 to n do begin
      readln(p,pi);
      if pi>w/2 then begin
        inc(t);
        l[t]:=p-sqrt(sqr(pi)-sqr(w/2));
        if l[t]<0 then l[t]:=0;
        r[t]:=p+sqrt(sqr(pi)-sqr(w/2));
        if r[t]>len then r[t]:=len;
        //writeln(l[t],' ',r[t]);
      end;
    end;
    qsort(1,t);
    now:=0;
    i:=1;
    tot:=0;
    flag:=true;
    while now<len do begin
      max:=0;
      while (l[i]<=now) and (i<=t) do begin
        if r[i]>max then max:=r[i];
        inc(i);
      end;
      if max=0 then begin
        writeln(-1);
        flag:=false;
        break;
      end;
      now:=max;
      inc(tot);
    end;
    if flag then writeln(tot);
  end;
end.
I test many cases,and it's no problem.But online-judge says "runtime error".I check the program over and over again,but i still can not find any mistake.could you help me?

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 10382 - Watering Grass

Post by AhmadKhatar » Tue Aug 28, 2012 2:11 pm

Hi!
I checked the code several times but I can't find any mistake in it. Does anybody know the problem with it?
Here is my code:

Code: Select all

#include <iostream>
#include <cmath>

using namespace std;

int n;
int sX [ 10000 ], sR [ 10000 ];
int l, w;
struct Line
{
	double l, r;
} ln [ 10000 ];

void process();
void construct();

int main()
{
	while ( cin >> n >> l >> w )
	{
		for ( int i = 0; i < n; i++ )
		{
			cin >> sX[ i ] >> sR[ i ];
		}
		process();
	}

	return 0;
}

void process()
{
	construct();

	double cV;
	cV = 0;
	
	Line tLn [ 10000 ];
	int tNo;

	int cnt = 0;
	while ( cV < l && n > 0 )
	{
		int next = -1;
		for ( int i = 0; i < n; i++ )
		{
			if ( next == -1 )
			{
				next = i;
			}
			else if ( (ln[ i ].l < ln[ next ].l) ||
				       (ln[ i ].l == ln[ next ].l && ln[ i ].r > ln[ next ].r) )
			{
				next = i;
			}
		}
		
		if ( ln[ next ].l > cV )
		{
			cout << -1 << endl;
			return;
		}
		cV = ln[ next ].r;
		cnt++;

		tNo = 0; // refresh
		for ( int j = 0; j < n; j++ )
		{
			if ( ln[ j ].l < cV )
			{
				if ( ln[ j ].r <= cV )
				{
					// do nothing
				}
				else
				{
					ln[ j ].l = cV;
					tLn[ tNo++ ] = ln[ j ];
				}
			}
			else
			{
				tLn[ tNo++ ] = ln[ j ];
			}
		}

		for ( int j = 0; j < tNo; j++ )
		{
			ln[ j ] = tLn[ j ];
		}
		n = tNo;
	}

	if ( cV < l )
	{
		cout << -1 << endl;
	}
	else
	{
		cout << cnt << endl;
	}
}

void construct()
{
	double tL, tR;
	int tCnt = 0;
	for ( int i = 0; i < n; i++ )
	{
		if ( sR[ i ] > w / 2.0 )
		{
			tL = max( sX[ i ] - sqrt( 4 * sR[ i ] * sR[ i ] - w * w + 0.0 ) / 2.0 , 0.0 );
			tR = min( sX[ i ] + sqrt( 4 * sR[ i ] * sR[ i ] - w * w + 0.0 ) / 2.0 , l + 0.0 );
			ln[ tCnt ].l = tL;
			ln[ tCnt ].r = tR;
			tCnt++;
		}
	}
	n = tCnt;
}
Thanks in advance! :D

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10382 - Watering Grass

Post by brianfry713 » Wed Aug 29, 2012 11:57 pm

You're having the same issue as Sanik in the post above yours. There's probably a case like:

Code: Select all

1 1000000001 100
1000000000 1000000000
Check input and AC output for thousands of problems on uDebug!

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 10382 - Watering Grass

Post by AhmadKhatar » Thu Aug 30, 2012 1:27 am

Many Thanks!
I got AC! :D

Post Reply

Return to “Volume 103 (10300-10399)”