Page 1 of 1

710 - The Game

Posted: Sun Jun 08, 2003 3:38 am
by Dmytro Chernysh
I read the description MANY times, but I can't get the Judge's output.
Maybe it's wrong?
Can somebody ilustrate me the answer?

Posted: Tue Jun 10, 2003 8:04 pm
by Dmytro Chernysh
No one can explain to me?
Maybe nobody understands either? :-)

Posted: Tue Sep 02, 2003 2:14 pm
by Dominik Michniewski
I think, that judge's answer is NUMBER of LINE SEGMENTS, which connect to given points :) but I get WA ...

Maybe other people could give us some IO tests ?

Best regards
DM

Posted: Tue Sep 02, 2003 6:09 pm
by little joey
Yes, it's the number of line segments (or the number of 90 degree turns Plus one). Did you notice that the input is given x1 y1 x2 y2, that is col1 row1 col2 row2, just the other way around than you'd normaly expect?
I can't think of special cases. Here's the complete list for the (1,1) piece in the example:

Code: Select all

5 4
XXXXX
X   X
XXX X
 XXX 
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 1 1 2
1 1 1 5
1 1 1 3
1 1 2 3
1 1 3 3
1 1 3 5
1 1 2 4
1 1 3 4
1 1 4 4
0 0 0 0
0 0
And the answer is:

Code: Select all

Board #1:
Pair 1: 1 segments.
Pair 2: 3 segments.
Pair 3: 3 segments.
Pair 4: 3 segments.
Pair 5: 1 segments.
Pair 6: 3 segments.
Pair 7: 3 segments.
Pair 8: impossible.
Pair 9: impossible.
Pair 10: 4 segments.
Pair 11: 3 segments.
Pair 12: impossible.
Pair 13: 4 segments.

Not Clear!

Posted: Wed Mar 03, 2004 7:11 am
by sohel
I can't seem to understand the 10th and 12th case that 'Little Joey' Posted.
Is the input coordinate 1 1 3 5 valid.. bcos I think 3 5 is not a position of a card.
and why is it 'impossible for the 12th .. since you can go out of the board can't you reach the destination.
:(

Posted: Wed Mar 03, 2004 8:38 am
by little joey
You are completely right, sohel. I must have had an off day back then :oops: :oops: :oops:
The input file was wrong and contained illegal pieces.
Here is the correct input (I hope ...)

Code: Select all

5 4
XXXXX
X   X
XXX X
 XXX 
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 1 1 2
1 1 5 2
1 1 1 3
1 1 2 3
1 1 3 3
1 1 5 3
1 1 2 4
1 1 3 4
1 1 4 4
0 0 0 0
0 0
And the output:

Code: Select all

Board #1:
Pair 1: 1 segments.
Pair 2: 3 segments.
Pair 3: 3 segments.
Pair 4: 3 segments.
Pair 5: 1 segments.
Pair 6: 4 segments.
Pair 7: 3 segments.
Pair 8: impossible.
Pair 9: impossible.
Pair 10: 4 segments.
Pair 11: 3 segments.
Pair 12: 4 segments.
Pair 13: 4 segments.

Still WA

Posted: Wed Mar 03, 2004 9:21 am
by sohel
Thanks for the rectification. Now the output matches with that of mine but i am getting WA.

I used BFS. While pushing into Queue I did not add any cost if it came from the same direction. Ie from 2 2 to 3 2 then to 4 2 would require one move. Is there anyting wrong.
:cry:

Posted: Wed Mar 03, 2004 11:42 am
by little joey
I use a modification of floodfill, which is a kind of BFS too. In principle your program should work.
What is your answer for the following case:

Code: Select all

14 7
XXXXXXXXXXXXXX
XX           X
X XXXXXXXXXX X
X XX         X
X  XX        X
XX           X
XXXXXXXXXXXXXX
2 2 5 5
0 0 0 0
0 0
It should be 3, not 5. That's the only kind of tricky case I can think of.
(Hope I got my numbers right this time...)

thanx

Posted: Wed Mar 03, 2004 1:23 pm
by sohel
Just got Ac.
My program actually gave 5 as the answer. I made the necessary modification and got AC.
Thanks, nevertheless.
8)

Posted: Thu Sep 20, 2007 4:39 pm
by Shmuma
I'm trying to solve this problem and constantly get WA.

I've checked all tests in this topic, could anyone post another tests?

Upd: got AC. Just output 'Impossible.' instead of 'impossible.' :D

Re: 710 - The Game

Posted: Mon Nov 10, 2008 7:43 am
by DD
little joey wrote:You are completely right, sohel. I must have had an off day back then :oops: :oops: :oops:
The input file was wrong and contained illegal pieces.
Here is the correct input (I hope ...)

Code: Select all

5 4
XXXXX
X X
XXX X
XXX 
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 1 1 2
1 1 5 2
1 1 1 3
1 1 2 3
1 1 3 3
1 1 5 3
1 1 2 4
1 1 3 4
1 1 4 4
0 0 0 0
0 0
And the output:

Code: Select all

Board #1:
Pair 1: 1 segments.
Pair 2: 3 segments.
Pair 3: 3 segments.
Pair 4: 3 segments.
Pair 5: 1 segments.
Pair 6: 4 segments.
Pair 7: 3 segments.
Pair 8: impossible.
Pair 9: impossible.
Pair 10: 4 segments.
Pair 11: 3 segments.
Pair 12: 4 segments.
Pair 13: 4 segments.
It is quite interesting that my outputs are different from yours :oops: , but I also got A.C.
My output:

Code: Select all

Board #1:
Pair 1: 1 segments.
Pair 2: 3 segments.
Pair 3: 3 segments.
Pair 4: 3 segments.
Pair 5: 1 segments.
Pair 6: 4 segments.
Pair 7: 3 segments.
Pair 8: 6 segments.
Pair 9: 5 segments.
Pair 10: 4 segments.
Pair 11: 4 segments.
Pair 12: 4 segments.
Pair 13: 4 segments.
I think the main reason for this phenomenon is that we have different definitions for boundary. But it also points out that the judge didn't have such test cases which needs to use the leftmost and rightmost boundary. 8)

Re: 710 - The Game

Posted: Wed May 06, 2015 5:17 pm
by Hikari9
For all solvers, do take note that the only moves you can do are left turn, right turn, and straight.