PROBLEM LINK: Better call Saul!
Setter: Yashodhan Agnihotri
Tester: Nishit Sharma , Aman Singhal
DIFFICULTY:
EASY
PREREQUISITES:
Games, Parity.
PROBLEM:
Given N stone piles with Ai stones in each pile, after X moves between two players, in which they remove one pile per move, find the winner of the game, if both of them play optimally.
Winner of the game depends on the final Sum parity of the stone piles.
EXPLANATION:
Let odd be the number of piles with odd-number of stones in it and even be the number of piles with even-number of stones in it. Here, remaining refers to N-X piles or the remaining number of piles after X moves.
Case 1
The player that plays last can win if there are both odd and even piles remaining.
Case 2
If Walter makes the last move and the remaining piles are even numbered, then Jesse should try to remove all odd or all even piles.
Case 3
If Jesse makes the last move and remaining are even, then Walter cannot win.
Case 4
If remaining are odd, Walter should try to remove all the even piles.
After including all the above cases, solution will run in O(n) complexity (due to counting of even and odd values).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, x, i;
cin >> n >> x;
vector<int> a(n);
int even = 0, odd = 0, ans = -1;
for (i = 0; i < n; i++) {
cin >> a[i];
if (a[i] & 1)odd++;
else even++;
}
if (x >= 2 * odd)ans = 0;
else if (x >= 2 * even)ans = (n - x) % 2;
else ans = x % 2;
if (!ans) cout << "Jesse\n";
else cout << "Walter\n";
}
return 0;
}
Tester's Solution (C++)
//#pragma GCC optimize "trapv"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define db double
#define mp make_pair
#define endl "\n"
#define f first
#define se second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define vll vector<ll>
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
ll add(ll x, ll y) {ll res = x + y; return (res >= MOD ? res - MOD : res);}
ll mul(ll x, ll y) {ll res = x * y; return (res >= MOD ? res % MOD : res);}
ll sub(ll x, ll y) {ll res = x - y; return (res < 0 ? res + MOD : res);}
ll power(ll x, ll y) {ll res = 1; x %= MOD; while (y) {if (y & 1)res = mul(res, x); y >>= 1; x = mul(x, x);} return res;}
ll mod_inv(ll x) {return power(x, MOD - 2);}
using namespace std;
int main()
{
quick;
int t;
cin >> t;
while (t--)
{
int n, x;
cin >> n >> x;
int a[n];
int cntodd = 0;
fab(0, n, i) {
cin >> a[i];
cntodd += (a[i] % 2);
}
int cnteven = n - cntodd;
int walterturns = (x + 1) / 2;
int jesseturns = (x / 2);
if (x % 2) {
if ( ((n - x) % 2 and cntodd > jesseturns) or ( (n - x) % 2 == 0 and (cnteven > jesseturns and cntodd > jesseturns) ) )
cout << "Walter" << endl;
else
cout << "Jesse" << endl;
}
else {
if (((n - x) % 2 and (cnteven > walterturns) ) or ( (n - x) % 2 == 0 ) )
cout << "Jesse" << endl;
else
cout << "Walter" << endl;
}
}
return 0;
}
Tester's Solution (Python)
import math
T=int(input())
for _ in range(T):
n,x=map(int,input().split())
A=list(map(int,input().split()))
ne=0
no=0
for i in A:
if (i%2==0):
ne=ne+1
else:
no=no+1
flag=0
if (no<=x//2):
flag=1
elif (ne<=x//2):
flag=(n-x+1)%2
else:
flag=(x+1)%2
if (flag==1):
print("Jesse")
else:
print("Walter")
For doubts, please leave them in the comment section, I’ll address them.
