PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
(The notation [x] is used for the floor function: [x] is the greatest integer not exceeding x.)
First off, non-integers are problematic, so consider that for any real numbers x, y, z with x+y=z, either
[x]+[y]=[z] or
[x]+[y]=[z]-1
Conversely, given a real number z and integers x’ and y’ satisfying either
x’+y’=[z] or
x’+y’=[z]-1,
then set x=(z+x’-y’)/2 and y=(z-x’+y’)/2 and we have [x]=x’, [y]=y’, and x+y=z.
Therefore we can restrict cuts to integer lengths, where the resulting logs from a cut sum to either the length of the original log, or the length of the original log minus one. Now the problem is solvable using Grundy numbers. For any length L, we calculate G(L)=mex({G(A) xor G(B) : (A+B=L or A+B=L-1) and A,B>0}). Then for a game with initial lengths of L1,…,LN if G(L1) xor … xor G(LN) is zero, Bob has a winning strategy. Otherwise Alice has a winning strategy.