## 10965 - Khepel's Problem

Moderator: Board moderators

luishhh
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain

### 10965 - Khepel's Problem

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;
}``````
"From lost to the river" --> Spanish quote

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
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!

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
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.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Hi,

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

Wojciech

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Hi tan_Tui!

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

However I got WA too!

Wojciech

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
My Accpetd Solution gives me:
• 96
99
96
93
93
99
95
9874
And there is no two sprinklers have same coordinates.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
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.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 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

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 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

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 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!

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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...

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 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.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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...

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 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.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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...