10923 - Seven Seas

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

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

10923 - Seven Seas

Post by Dreamer#1 » Sat Oct 01, 2005 6:06 pm

I think I'm missing something in this problem. I saw dozens of people solved it in online contest but I find the problem unclear.
The enemy ships are pretty dumb, so that they will always move to the closest position they can get to you, ...
Consider the following situation at some portion of the board after my move:

Code: Select all

S..
..E
 
Now where will the E move? There are two possibilities:

Code: Select all

SE.
...

OR,

S..
.E.
 
Can someone please explain which one should we consider and why?

Thanks in advance. :)

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sun Oct 02, 2005 3:02 am

sorry i forgot to login... :D

liux0229
New poster
Posts: 8
Joined: Thu May 20, 2004 1:30 pm
Location: China

Post by liux0229 » Sun Oct 02, 2005 5:52 am

hi, Dreamer#1!
It was my post. Although I knew it was euclidean distance but I've kept getting WA since the contest. I was here for some hint on where could be wrong but only to find your post. Since you've got AC, can you post some input/output here?

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sun Oct 02, 2005 9:25 pm

not much......but u can try this.
input:

Code: Select all

7

........
........
........
.#E...E#
.#.....#
.#.....#
.#S....#
.#######
........

E......E
........
........
........
...S....
........
........
........
E......E


........
........
........
.#E...E#
.#.#.#.#
.#.###.#
.#S....#
.#######
........

........
...#....
........
..#.....
........
........
..S.....
........
........

........
.E.#....
...E....
..#.....
........
........
..S.....
........
........

........
.E.E....
...S....
.E..E...
........
........
........
........
........

E......#
........
........
........
........
........
........
.......S
#.......

output:

Code: Select all

I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!
Jalal : AIUB SPARKS

liux0229
New poster
Posts: 8
Joined: Thu May 20, 2004 1:30 pm
Location: China

Post by liux0229 » Mon Oct 03, 2005 11:58 am

Sorry, it was me

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Wed Oct 05, 2005 9:20 am

is the soln a straight forward BFS?? but 8^10 is much bigger (in worst case) nay kinda huristic needed??
Self judging is the best judging!

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Wed Oct 05, 2005 9:29 am

shanto86 wrote:is the soln a straight forward BFS?? but 8^10 is much bigger (in worst case) nay kinda huristic needed??

no, wise DFS (recursive) is enough.
Sorry For My Poor English.. :)

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Thu Oct 06, 2005 10:44 pm

Hello there!

I have got correct answers for all the inputs of this board, but I get WA from OJ.

Could anyone say me if are there some tricky inputs?
And, could anyone say me if is this correct?

input:

Code: Select all

8	
.....S..
........
........
########
E......E
........
....E...
........
EEE.....

.....S..
........
........
........
E......E
........
....E...
........
..E.....

.....S..
........
........
........
........
........
........
E......E
........

.....S..
........
........
........
E......E
........
........
........
........

.....S..
........
........
........
........
E......E
........
........
........

E....S..
........
........
........
........
........
....E...
........
EEE.....

.....S..
........
........
........
........
..E.....
....E...
........
........

.....S..
........
.....#..
........
........
..E.....
....E...
........
........
output:

Code: Select all

I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
Thanks in advance!

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Oct 07, 2005 3:17 am

My output:

Code: Select all

I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
No trick at all. A simple DFS will do.

[EDIT:] Please ignore my output, it's wrong and Emilio's output is correct.
Last edited by Cho on Sat Oct 08, 2005 9:02 am, edited 2 times in total.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Fri Oct 07, 2005 8:16 pm

Hi another time!

I can't figure out how you can destroy the enemies in the fourth case without dead.
Could you explain me that?

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

Post by little joey » Fri Oct 07, 2005 10:14 pm

Strange, my program gives the same answers as Emilio's.
I'd be interested how the ship can escape in cases 4 and 6.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Fri Oct 07, 2005 10:50 pm

My AC program also gives the same answers as Emilio's.

btw. In case 4 you can escape if you allow the ship to go 'outside the area', but I don't see how you can escape in case 6.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Oct 08, 2005 1:52 am

Thanks!

I have got AC. My trouble was a bug in my code.

But I have got AC with different approachs:
1. I calculate the distance how euclidean distance.
2. I calculate the distance how Manhattan distance.
3. I can move (only test with my own ship) where there is a rock.
4. I can't move (only test with my own ship) where there is a rock.
5. A mixture of them.

Strange?

I think test cases are poor or other things...

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Oct 08, 2005 8:59 am

There is a bug in my previously AC-ed code, so the output of my previous post is wrong.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

10923 - Seven Seas

Post by Solaris » Mon Feb 06, 2006 10:10 am

This code runs ok in my VC 6.0 but shows CE in the OJ ... I have removed the sort function and then the CE is removed. Can any one tell me why this happens ?? (I have overloaded the < operator, and this should run ok, I want to know why not)

Code: Select all

You do not want to get AC in 1.5 seconds in this problem

I have already got AC in this problem by omitting the sort function. But I am surprised to see some near zero second solves in this problem. Is there any greedy approach (or any other approach than DFS) to solve this problem ?? Thanx in advance for any hint that anyone can give.

Perdon my bad english :P
Last edited by Solaris on Mon Feb 06, 2006 7:35 pm, edited 1 time in total.
Where's the "Any" key?

Post Reply

Return to “Volume 109 (10900-10999)”