Hello Codeforces Community. I came up with a problem for you today. Hope you enjoy it!
Problem :
Given two integers $$$N$$$, and $$$K$$$. Two players A and B play a game on a grid of size $$$1\cdot K$$$. Each player has $$$N$$$ token.
We define a good sequence $$$c = [c_1,c_2,...,c_K]$$$ as a sequence of positive integers of length $$$K$$$, and its sum is equal to $$$N$$$, i.e, $$$c_1+c_2+...+c_K = N$$$.
Player A goes first, He chooses a good sequence $$$a$$$ (How he will partition his tokens on the grid). Then player B goes second, and chooses another good sequence $$$b$$$.
Let $$$s_i = b_i+b_{i+1}+...+b_K$$$. We define the value of the game as $$$\displaystyle T(a,b) = \sum_{k=1}^K k\cdot a_k \cdot s_k$$$.
We also define the value of the sequence $$$b$$$ as $$$Val(b) = max(\{T(u,b)$$$ $$$/$$$ $$$u$$$ is a good sequence $$$ \})$$$.
Finally, the score of the game is $$$\displaystyle Score(a,b) = \frac{T(a,b)}{Val(b)}$$$.
Player A is trying to maximize the score of the game, while player B is trying to minimize it.
If both players are playing optimally, find the maximal score that player A can achieve, and the sequences $$$a$$$ and $$$b$$$ to achieve it.
Smaller cases : find the maximal score for $$$K=10$$$ and $$$N=100$$$, and the sequences $$$a$$$ and $$$b$$$ to achieve it.
Generalization of the problem :
We define a good sequence as a sequence $$$c = [c_1,c_2,...,c_K]$$$ such that $$$c_1+c_2+...+c_K=1$$$ and $$$c_i \in [0,1]$$$ for $$$1\le i \le K$$$. Find the maximal score that player A can achieve, and the sequences $$$a$$$ and $$$b$$$ to achieve it. (The process of the game is the same)