710 - The Game
Moderator: Board moderators
-
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
710 - The Game
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?
Maybe it's wrong?
Can somebody ilustrate me the answer?
-
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
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
![:)](./images/smilies/icon_smile.gif)
Maybe other people could give us some IO tests ?
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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:
And the answer is:
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
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!
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.
![:(](./images/smilies/icon_frown.gif)
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.
![:(](./images/smilies/icon_frown.gif)
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
You are completely right, sohel. I must have had an off day back then
The input file was wrong and contained illegal pieces.
Here is the correct input (I hope ...)
And the output:
![:oops:](./images/smilies/icon_redface.gif)
![:oops:](./images/smilies/icon_redface.gif)
![:oops:](./images/smilies/icon_redface.gif)
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
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
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:](./images/smilies/icon_cry.gif)
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:](./images/smilies/icon_cry.gif)
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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:
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...)
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
(Hope I got my numbers right this time...)
-
- Experienced poster
- Posts: 145
- Joined: Thu Aug 14, 2003 8:42 am
- Location: Mountain View, California
- Contact:
Re: 710 - The Game
It is quite interesting that my outputs are different from yourslittle joey wrote:You are completely right, sohel. I must have had an off day back then![]()
![]()
![]()
The input file was wrong and contained illegal pieces.
Here is the correct input (I hope ...)
And the output: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
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.
![:oops:](./images/smilies/icon_redface.gif)
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.
![8)](./images/smilies/icon_cool.gif)
Have you ever...
- Wanted to work at best companies?
- Struggled with interview problems that could be solved in 15 minutes?
- Wished you could study real-world problems?
Re: 710 - The Game
For all solvers, do take note that the only moves you can do are left turn, right turn, and straight.