710 - The Game

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

Moderator: Board moderators

Post Reply
Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

710 - The Game

Post by Dmytro Chernysh » Sun Jun 08, 2003 3:38 am

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?

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Tue Jun 10, 2003 8:04 pm

No one can explain to me?
Maybe nobody understands either? :-)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Sep 02, 2003 2:14 pm

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
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)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Sep 02, 2003 6:09 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:

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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Not Clear!

Post by sohel » Wed Mar 03, 2004 7:11 am

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.
:(

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Mar 03, 2004 8:38 am

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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Still WA

Post by sohel » Wed Mar 03, 2004 9:21 am

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:

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Mar 03, 2004 11:42 am

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...)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

thanx

Post by sohel » Wed Mar 03, 2004 1:23 pm

Just got Ac.
My program actually gave 5 as the answer. I made the necessary modification and got AC.
Thanks, nevertheless.
8)

Shmuma
New poster
Posts: 1
Joined: Thu Sep 20, 2007 4:35 pm

Post by Shmuma » Thu Sep 20, 2007 4:39 pm

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

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 710 - The Game

Post by DD » Mon Nov 10, 2008 7:43 am

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)
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?
If so, you need to read Elements of Programming Interviews.

Hikari9
New poster
Posts: 20
Joined: Tue Jan 22, 2013 4:39 pm

Re: 710 - The Game

Post by Hikari9 » Wed May 06, 2015 5:17 pm

For all solvers, do take note that the only moves you can do are left turn, right turn, and straight.

Post Reply

Return to “Volume 7 (700-799)”