PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: shivanshj
Tester & Editorialist: iceknight1093
DIFFICULTY:
2628
PREREQUISITES:
Observation
PROBLEM:
Shivansh and Tina play a game; Shivansh goes first.
They have a number with them, initially N. On their turn, a player should pick a non-negative integer power of K that doesn’t exceed N, and subtract it from N.
Under optimal play, who wins?
EXPLANATION:
With two-player games like this, It often helps to analyze some small cases first, for example with K = 2, 3, 4, \text{ or } 5.
Some simple analysis reveals that when K = 3, Shivansh can always win if N is odd, and loses otherwise.
This is because 3^x is odd no matter what the value of x is. So:
- If N is odd, an odd number of turns will have passed when N reaches zero.
This means Shivansh made the last move. - If N is even, an even number of turns will have passed when N reaches zero.
This means Tina made the last move.
In fact, the above analysis holds true for all odd K: Shivansh wins if N is odd, and loses otherwise.
For even K, let’s look at what happens for small N.
Clearly, Shivansh can win if N = 1, 3, 5, 7, \ldots, K-1 and Tina can win N = 0, 2, 4, 6, 8, \ldots, K-2.
That’s because for these values of N, the only possible move is to subtract 1; so the winner is decided by parity.
However, Shivansh can win N = K by just subtracting K.
After this,
- Tina wins N = K+1, since Shivansh must subtract either 1 or K and Tina subtracts the other one.
- Shivansh wins N = K+2, by subtracting 1 and giving N = K+1 (a losing state) to Tina.
- Tina wins N = K+3: whether he subtracts K or 1, 3 and K+2 are both winning states for Tina.
- Generally, Tina wins K+1, K+3, K+5, \ldots, 2K-1; and Shivansh wins K+2, K+4, \ldots, 2K
- However, Shivansh wins 2K+1; since he can subtract K on his turn and give K+1 to Tina (which is losing, as noted above)
You might notice that this process is consistent in ‘blocks’ of length K+1 starting from 0.
That is, in each such block, Tina wins the even positions and Shivansh wins the odd ones; except Shivansh wins the last position despite it being even.
This is indeed the pattern for Shivansh’s win condition.
That is, let r = N \pmod {K+1}, i.e, r is the remainder when N is divided by K+1.
Then, Shivansh wins if r is odd or r = K, and loses otherwise.
Proof
We’ll prove this by induction, though the basic idea was outlined above.
For the base case, we already know it’s true for the segment [0, K+1), as noted above.
Now, assume it’s true for [0, x\cdot(K+1) ), and we’ll prove it’s true for [0, (x+1)\cdot(K+1)).
The main observation required here is the fact that K^x is always either 1 or -1 modulo (K+1), which is easy to see (in fact, since K \equiv -1 \pmod {K+1}, the powers of K alternate between 1 and -1).
So,
- x\cdot (K+1) is a losing state: no matter what move is made, we move to either 1 \pmod{K+1} or K \pmod {K+1}, and in the range \left[0, x\cdot (K+1)\right); by the inductive hypothesis these are winning states for the opponent.
- x\cdot (K+1) + 1 is a winning state: subtract 1 to put the opponent in a losing state.
- x\cdot (K+1) + 2 is a losing state: either we subtract 1 and move to (x\cdot (K+1)+1), which is winning for the opponent; or we subtract move to an odd value modulo K+1 in the range [0, x\cdot (K+1)) which is still winning for the opponent.
- Extrapolating this, all odd numbers are winning and even numbers are losing.
- However, x\cdot (K+1) + K is winning, since we can subtract K.
This takes care of all integers in the range [x\cdot (K+1), (x+1)\cdot (K+1)); and so we’re done.
In fact, this pattern holds true for odd K as well, since we didn’t really use the parity of K anywhere.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Author's code (C++)
//Enjoying CP as always!
// NO FAREWELL: KEEP GOOGLE COMPETITIONS ALIVE
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
//freopen("small_tests_input.txt", "r", stdin);
//freopen("small_tests_output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--) {
int n,k;
cin>>n>>k;
int z = n%(k+1);
if((z&1LL) || z==k) {
cout<<"Shivansh\n";
} else {
cout<<"Tina\n";
}
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
print('Shivansh' if n%(k+1) == k or (n%(k+1))%2 == 1 else 'Tina')
). Have you read the editorial and proof?