There are pieces of sushi on a table. Each piece is either raw or cooked, as described by a string : is R for raw sushi and C for cooked sushi. Piece initially has a score of .
Alice and Bob take turns, with Alice going first. On each turn, the player eats any one remaining piece of sushi and adds its current score to their total. Then the score of every remaining cooked piece decreases by . The scores of raw pieces do not change.
The game ends when all pieces have been eaten. Alice wants to maximize her total score minus Bob's total score, while Bob wants to minimize this difference.
Find the final difference if both players play optimally.
A piece's score may become negative. It must still be eaten before the game ends, and eating it adds that negative score to the player's total. Neither player may skip a turn.
R and C.Alice eats the only piece and gains points. Bob gains , so the difference is .
Alice eats the cooked piece first and gains . Bob and Alice then each eat one raw piece worth , giving a difference of . If Alice starts with a raw piece instead, Bob can eat the other raw piece, leaving the cooked piece worth for Alice; that choice gives only .
One optimal play takes pieces with scores , in that order. Alice gains and Bob gains , so the difference is .
All remaining pieces always have the same score. The scores gained on successive turns are . Alice totals , Bob totals , and the difference is .
Alice can eat a cooked piece first. Bob then eats the raw piece for , leaving a cooked piece worth for Alice, for a difference of . Instead, Alice can start with the raw piece: the two cooked pieces are then eaten for and , giving a difference of . Thus optimal play gives .