# PROBLEM LINK: Better call Saul!

* Setter:* Yashodhan Agnihotri

*Nishit Sharma , Aman Singhal*

**Tester:**# DIFFICULTY:

EASY

# PREREQUISITES:

Games, Parity.

# PROBLEM:

Given N stone piles with A_{i} 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.