CF1987D World is Mine

Alice and Bob are playing a game. Initially, there are $ n $ cakes, with the $ i $ -th cake having a tastiness value of $ a_i $ . Alice and Bob take turns eating them, with Alice starting first: - In her turn, Alice chooses and eats any remaining cake whose tastiness is strictly greater than the maximum tastiness of any of the cakes she's eaten before that. Note that on the first turn, she can choose any cake. - In his turn, Bob chooses any remaining cake and eats it. The game ends when the current player can't eat a suitable cake. Let $ x $ be the number of cakes that Alice ate. Then, Alice wants to maximize $ x $ , while Bob wants to minimize $ x $ . Find out how many cakes Alice will eat if both players play optimally.

N/A

N/A

In the first test case, one possible sequence of turns is: 1. Alice eats a cake with a tastiness value of $ 1 $ . The remaining cakes are $ [4, 2, 3] $ . 2. Bob eats a cake with a tastiness value of $ 2 $ . The remaining cakes are $ [4, 3] $ . 3. Alice eats a cake with a tastiness of $ 3 $ . The remaining cakes are $ [4] $ . 4. Bob eats a cake with a tastiness value of $ 4 $ . The remaining cakes are $ [] $ . 5. Since there are no more cakes left, the game ends. In the second test case, one possible sequence of turns is: 1. Alice eats a cake with a tastiness value of $ 1 $ . The remaining cakes are $ [1, 1] $ . 2. Bob eats a cake with a tastiness value of $ 1 $ . The remaining cakes are $ [1] $ . 3. Since Alice has already eaten a cake with a tastiness value of $ 1 $ , she cannot make a turn, so the game ends.