Dice and Sum

Sort the three values as $x\leq y\leq z$. The sum of differences equals $(y-x)+(z-x)+(z-y)=2(z-x)$. Thus an odd $K$ gives zero triples. If $K=0$, all values must be equal, giving $N$ triples.

Otherwise, let $d=K/2>0$. If $d\geq N$, the answer is zero. For $d<N$, the minimum $x$ has choices, and the maximum is . There are strictly intermediate values, each giving six permutations. If the middle value equals either endpoint, each of the two choices gives three permutations. Hence each minimum contributes triples, and the answer is .

Subtask 1: enumerate every ordered triple in $O(N^3)$ time and $O(1)$ extra space. Subtask 2: evaluate the formula in $O(1)$ time and $O(1)$ extra space.

The maximum answer is $6\lfloor N^2/4\rfloor\leq 1\,500\,000\,000\,000\,000\,000$. All required arithmetic fits in signed 64-bit integers. Avoid 32-bit multiplication and floating-point arithmetic.

Solution written by GPT