Glass Bead Game
All submissions for this problem are available.
You play the following game against a devilishly clever opponent. On the table, there are two bowls ﬁlled with glass beads. In each move, depending on whose turn it is, you or your opponent can do one of the following.
- Move one bead from the ﬁrst bowl to the second bowl
- Remove one bead from the second bowl.
At any point in the game, let x denote the number of beads in the ﬁrst bowl and y denote the number of beads in the second bowl. If x + y is even, it is your turn to move. If x + y is odd, it is your opponent’s turn to move
At each position of the game, you get some points that depend on the number of beads, x and y, in the two bowls. This is given by a function f(x, y) = Ax2 + By2 + Cxy, where A, B and C are integers that are ﬁxed each time the game is played.
The game starts with M beads in the ﬁrst bowl and N beads in the second bowl. As the game progresses, beads are removed. The game ends when both bowls are empty.
Your score for the game is the sum of the values f(x, y) for each position (x, y) that the game passes through, starting from (M, N) and ending with (0, 0). Your aim is to obtain as high a score as possible, no matter what moves your opponent chooses. Remember that your opponent is ﬁendishly ingenious and will always play in such a way as to minimize your score.
For example, suppose the game starts with 2 beads in each bowl and the score function is f(x, y) = x2 − y2 − xy: that is, A = 1, B = −1 and C = −1. Here are some plays of the game—the positions where you choose the move are enclosed in boxes and the positions where your opponent moves are not enclosed in boxes.
In this particular game, the best possible score that you can achieve if you consider all possible moves that your opponent can choose is −22. Recall that your devilishly clever opponent always plays in such a way that your score is minimized.
The input consists of a single line containing ﬁve integers, M, N, A, B and C where M and N are the number of beads initially in the ﬁrst and second bowl, respectively and A, B and C are the coeﬃcients of the score function f(x, y) = Ax2 + By2 + Cxy.
The output should be a single integer, the maximum score that you can achieve in this game.
- 1 ≤ M,N ≤ 600
2 2 1 -1 -1
|Tags||easy, greedy, inpr1502, yogesh01|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.