Page 1 of 2

### 10965 - Khepel's Problem

Posted: Mon Nov 14, 2005 11:07 pm
Hi
I think this problem is badly specified, basically I don't know how to handle questions such: does [0,1] overlaps [1,2]? I consider the time the cat is sleeping as a closed interval, as well as the times the sprinklers are pouring water in each cell. Maybe this approach is wrong and I should have considered open intervals.
This is the function I think is the main task:

Code: Select all

``````int overlap (int c, int d, int module) {
/*return 1 if there exist x in [a,b] such that x mod module is in the interval [c,d] (c,d<module), else return 0*/
if (b - a >= module) return 1;
b %= module;
a %= module;
if (a < c)
if (b >= a && b < c) return 0;
else return 1;
else if (a > d)
if (b >= a && b < module || b < c) return 0;
else return 1;
return 1;
}``````

Posted: Tue Nov 15, 2005 1:01 am
As in problem statement, time interval for each sprinklers begin at time=0
and if a sprinkler has period p then, according to one-cycle movement, that sprinkler will pour water at it`s first direction for [0,p) and in time p it changes its direction without pouring water!

Posted: Fri Nov 18, 2005 8:50 pm
Hi, everyone.
I got WA several times.
The reason may be my misunderstanding about the problem description like as him.

Would you give me the correct answer for following input?

Code: Select all

``````10 10 1
5 5 8 3 N
7 8
10 10 1
5 5 8 3 N
8 8
10 10 1
5 5 8 3 N
8 9
10 10 1
5 5 8 3 N
8 23
10 10 1
5 5 8 3 N
8 24
10 10 1
10 10 1 3 E
8 10
10 10 1
5 5 1 1 N
0 1000000000
100 100 4
5 5 1000000 1 N
100 5 1000000 98 W
30 30 900000 5 E
30 30 900000 1 N
3456789 6000000
0 0 0
``````
My output is :

Code: Select all

``````96
96
96
93
93
99
95
9874
``````
Thank you.

Posted: Sat Nov 19, 2005 11:22 pm
Hi,

Another question: Is it possible that 2 sprinklers have the same coordinates (but maybe different R and/or d)?

Wojciech

Posted: Sun Nov 20, 2005 3:59 pm
Hi tan_Tui!

For Your input my code gives:
96
99
99
93
93
99
95
9874

However I got WA too!

Wojciech

Posted: Sun Nov 20, 2005 4:52 pm
My Accpetd Solution gives me:
• 96
99
96
93
93
99
95
9874
And there is no two sprinklers have same coordinates.

Posted: Mon Nov 21, 2005 12:29 pm
I read my code again and improved, then got same answer as Moha output.

What is correct answer for this input?
And, if you have some special input set, please show me...

Code: Select all

``````10 10 1
5 5 8 3 N
9 17
10 10 1
5 5 8 3 N
17 17
10 10 1
5 5 8 3 N
18 18
10 10 1
5 5 8 3 N
26 26
10 10 1
5 5 8 3 N
0 0
10 10 1
5 5 1 3 N
1 1
10 10 1
5 5 8 3 N
16 18
0 0 0
``````
My code outputs :

Code: Select all

``````96
99
96
99
96
99
93
``````
Best regards.

Posted: Mon Nov 21, 2005 8:13 pm
My program gives the same output as yours but I got WA too. I've no idea what could be the problem now.

Wojciech

Posted: Mon Nov 21, 2005 9:30 pm
Hi tan_Yui!

I had a problem with inputs like this:
1 10 1
1 1 1 3 E
1 8
10 1 1
10 1 1 3 S
5 12
0 0 0
The correct output is:
6
6

Now I got AC

Thanks to Moha and tan_Yui!

Wojciech

Posted: Tue Nov 22, 2005 5:43 am
Hello, "w k".
Your input was just a critical input of my code!
After changed to correspond, I could get Accepted!
Thank you, "w k" and Moha!

Posted: Thu Nov 24, 2005 9:57 am
I think problem statement is ambigous.

Coordinaters of sprinklers are given as <row> <column>

But size of the field as <number of columns> <number of rows>

I realize it only after online contest...

Posted: Thu Nov 24, 2005 10:18 am
kp wrote:I think problem statement is ambigous.

Coordinaters of sprinklers are given as <row> <column>

But size of the field as <number of columns> <number of rows>

I realize it only after online contest...
...? I can't find your problem.
The first line of each test case contains 3 integers 1<=m,n<=100 (the dimensions of the garden), and 0<=k<=1000 which is the number of sprinklers in it. The next lines each consist of 4 non negative integers r,c,p,R and a character d. 1<=r<=m and 1<=c<=n indicate the coordinates of the i-th sprinkler in row-column format ......
refer to : http://online-judge.uva.es/contest/data ... et/p1.html

Best regards.

Posted: Thu Nov 24, 2005 10:40 am
My problem was that I considered m is a number of rows and n number of columns! (row-column format). When I saw here last post by w k I realized that m is a number of columns!

After changing

Code: Select all

``````  for i:=1 to m do
for j:= 1 to n do
``````
to

Code: Select all

``````  for i:=1 to n do
for j:= 1 to m do
``````
I got AC

Sample test was a square so nothing was suspicious...

Posted: Thu Nov 24, 2005 11:44 am
kp wrote:My problem was that I considered m is a number of rows and n number of columns! (row-column format). When I saw here last post by w k I realized that m is a number of columns!
Because my AC code is handled m and n as row-column format,
I think it is your code own problem.
And, I think the last post of "w k" didn't say about such things.
I want to know other solver's opinion too.

Best regards.

Posted: Thu Nov 24, 2005 2:52 pm
tan_Yui wrote:
kp wrote:My problem was that I considered m is a number of rows and n number of columns! (row-column format). When I saw here last post by w k I realized that m is a number of columns!
Because my AC code is handled m and n as row-column format,
I think it is your code own problem.
And, I think the last post of "w k" didn't say about such things.
I want to know other solver's opinion too.

Best regards.
Damn, you right!

I can't believe me so stuppid

my code starts like this:

Code: Select all

``````  readln(n,m,k);
``````
but it should be

Code: Select all

``````  readln(m,n,k);
``````
Thats how I sometimes get WA during contest...