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

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

10923 - Seven Seas

Post by Dreamer#1 »

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

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

Post by Dreamer#1 »

sorry i forgot to login... :D

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

Post by liux0229 »

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?

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

Post by CodeMaker »

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 »

Sorry, it was me

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

Post by shanto86 »

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 »

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 »

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!

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

Post by Cho »

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 »

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?

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

Post by little joey »

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 »

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 »

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

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

Post by Cho »

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 »

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