10965 - Khepel's Problem

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

Moderator: Board moderators

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

10965 - Khepel's Problem

Post by luishhh » 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;
}
"From lost to the river" --> Spanish quote

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » 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!

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » 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.

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

Post by w k » 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

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

Post by w k » 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

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » 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.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Mon Nov 21, 2005 12:29 pm

Thank you for your reply, "Moha", "w k"!
I read my code again and improved, then got same answer as Moha output.
...but I keep judge WrongAnswer.

Please help again.
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

Post by w k » 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

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

Post by w k » 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 :lol:

Thanks to Moha and tan_Yui!

Wojciech

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » 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! :D
Thank you, "w k" and Moha!

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » 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...

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » 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.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » 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...

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » 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.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » 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... :lol:

Post Reply

Return to “Volume 109 (10900-10999)”