-
July 26th, 2015, 03:56 AM
#1
Algorithm for simple board game
We have N coins of type-1 and M coins of type-2. A game-board has N squares of type-1 and M squares of type-2. In this game we must place one coin into each square. After placing all coins we will get a score based on our coin placement strategy .
If type-1 square contains a type-1 coin then we will get A points, if type-2 square contains a type-2 coin then we will get B points and in all other cases, we will get C points.Our total game score will be sum of scores of all squares.
Inputs Available are ( N,M,A,B,C )
How can we maximize our score ?
-
July 27th, 2015, 07:20 AM
#2
Re: Algorithm for simple board game
Originally Posted by aakashjsr
How can we maximize our score ?
We can start by putting all N type-1 coins on the N type-1 squares and all M type-2 coins on the M type-2 squares. The score becomes,
Score = N*A + M*B + 0*C
Can we improve on this? Yes we can swap one type-1 coin with one type-2 coin. The score becomes,
Score = (N-1)*A + (M-1)*B + 2*C
Did it pay off? Well we lost A+B but gained 2*C so if
2*C > A+B
we gained more than we lost. And if we gained something by this one-coin swap we can gain even more by swapping as many coins as possible.
So first we must find out whether swapping pays off at all (otherwise we already have the maximum score). If it pays off indeed we must figure out what is the biggest swap we can make and calculate the score for that.
Last edited by tiliavirga; July 27th, 2015 at 07:50 AM.
-
July 27th, 2015, 07:26 AM
#3
Re: Algorithm for simple board game
this is a simple math problem.
all coins into the 'right' squares gives a total score of N*A+M*B
as many coins as possible into the 'wrong' squares is 2*min(N,M)*C + (N-min(N,M))*A + (M-min(N,M))*B
follow whichever of the above 2 possibilities gives the highest value
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|