Define a state satisfying the following conditions to be a “\(P\) state”:

\[m = \min_i A_i, m \equiv 0 \pmod{K}, \sum_i (A_i - m) \lt K\]

The following three propositions hold regarding \(P\) states.

If the operation cannot be performed \(K\) times on a turn \(\to\) it is a \(P\) state

When the operation cannot be performed \(K\) times, the total number of stones is less than \(K\). Since this is fewer than the number of piles, there exists a pile with zero stones. Thus, \(m=0\) and \(\sum_i (A_i - m) \lt K\) hold, satisfying the condition for state \(P\).

It is impossible to move from a \(P\) state to a \(P\) state

Suppose it were possible to move from a \(P\) state to another.
As a property of \(P\) states, letting the minimum value of the current \(P\) state be \(tk\), from the condition \(\sum_i (A_i-tk) \lt K\), we have:

\[\forall i, tk \leq A_i \lt (t+1)k.\]

If it were possible to move from a \(P\) state to another in one turn, there must be at least one pile whose number of stones does not change, so the minimum value \(tk\) would need to remain unchanged. However, since \(\sum_i (A_i-tk) \lt K\) holds before the move, such an operation cannot be performed \(K\) times, which is a contradiction.

From a state that is not a \(P\) state, it is always possible to move to a \(P\) state

Let the current minimum value be \(m = qK + r, 0 \leq r \lt K\), and let \(j\) denote one of the piles attaining the minimum value.
We case split on whether \(r = 0\).
If \(r \gt 0\), it suffices to reduce the number of stones of the piles other than pile \(j\) down to \(qK\). If \(r = 0\), it suffices to leave pile \(j\) unchanged and reduce the other piles down to \(m\). (Since the original state is not a \(P\) state, we have \(\sum_i (A_i - m) \geq K\), so this can be achieved by performing the operations appropriately.)
Thus, in either case, it is possible to move to a \(P\) state.

From the above, we have shown that

• If a turn cannot be completed \(\to\) it is a \(P\) state
• It is not possible to move from a \(P\) state to another
• From a state that is not a \(P\) state, it is always possible to move to a \(P\) state

Thus, it has been shown that the \(P\) states are exactly the losing states for the player to move. Put simply, a player whose turn comes around in a state that is not a \(P\) state has a winning strategy of moving to a \(P\) state. Whether the initial state is a \(P\) state can be computed in \(\mathrm{O}(K)\).

• Sample implementation (C++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int T;
  cin >> T;
  while (T--) {
    int K;
    cin >> K;
    vector<int> A(K + 1);
    for (auto& a : A) cin >> a;
    int m = *min_element(begin(A), end(A));
    long long S = 0;
    for (auto& a : A) S += a - m;
    if (m % K == 0 && S < K) {
      cout << "Bob" << "\n";
    } else {
      cout << "Alice" << "\n";
    }
  }
}