A Game
There are a bunch of coins on a table, laid out in a straight line.Each coin has a (positive) value from 1 to 1000. Now, you're going to play a game with a friend.
At every turn, you must remove a coin from one end of the line.
Turns alternate, so your friend goes immediately after you're done.
The game ends when there are no coins remaining.
An example game:
The coins start like this:
4 4 9 4
You always go first, so you take the 4 from the left side:
4 9 4
Your friend takes any of the 4s (it doesn't matter)
9 4
Now you can take the 9, and your friend takes the remaining 4.
Your score, in this case, is 4+9 = 13.
(In this case you can always beat your friend.)
Find the maximum possible score you can achieve.
Input
N <= 1000, the number of coins.N lines, each with the value of a coin.
Output
Your maximum possible score, provided that you go first and your friend plays perfectly.
All Submissions
Best Solutions
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
Is it like the game of nim where your friend is thinking ahead all the way to the end?
That being said, you are making a mistake in your BFS that will come back to bite you in other problems. Specifically, you are storing far, far more state than necessary in your queue. You can in fact store the problem state in two integers, whereas your code is storing as many as 1003 integers plus the overhead of a linked list.
If you can figure out how to store the state more compactly, it might push you towards a more sane solution.
Thanks. :D