Last Updated on June 17, 2022 by Ria Pathak
CONCEPTS USED:
Game theory
DIFFICULTY LEVEL:
Medium.
PROBLEM STATEMENT(SIMPLIFIED):
Nishant wants to play games with his friend. Now this time Nishant made an array of integers. So in each turn players can choose any two integers and replace them with sum or product of those integers. When there is only one element left if that element is even then Nishant wins else his friend wins. Both players play optimally.
See original problem statement here
For Example :
Input
1
5 Nishant
1 2 3 4 5
Output
FriendOBSERVATION:
The strategy for nishant is to leave behind one even number and that for friend is to leave odd for himself.
SOLVING APPROACH:
To make the sum or product odd, one odd element is suffient .
If you get the other element also odd,then the product becomes odd.
Else the sum becomes odd.
Follow the code:
SOLUTION:
#include <bits/stdc++.h>
using namespace std;
const string AR = "Nishant";
const string FR = "Friend";
string solve() {
int n;
string name;
cin>>n>>name;
bool st = (name == "Nishant");
int in[n];
for(int i = 0; i < n; ++i)
cin>>in[i];
if(n == 1)
return in[0] % 2 ? FR : AR;
if(st == (n % 2 == 0))
return AR;
int cnt = 0;
for(int i = 0; i < n; ++i)
if(in[i] % 2) {
++cnt;
++i;
}
if(cnt >= (n + 1) / 2)
return FR;
return AR;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cout<<solve()<<"\n";
}
return 0;
}
import java.util.Scanner;
class PlayGames
{
static String AR="Nishant";
static String FR="Friend";
static Scanner sc=new Scanner(System.in);
static String solve()
{
int n=sc.nextInt();
String name=sc.next();
boolean st=(name== "Nishant");
int in[]=new int[n];
for(int i=0;i<n;i++)
{
in[i]=sc.nextInt();
}
if(n==1)
{
return in[0]%2 == 0 ? FR : AR;
}
if(st == (n % 2 == 0))
return AR;
int cnt = 0;
for(int i = 0; i < n; ++i)
if(in[i] % 2 ==0)
{
++cnt;
++i;
}
if(cnt >= (n + 1) / 2)
return FR;
return AR;
}
public static void main(String[] args)
{
int t=sc.nextInt();
while(t!=0)
{
System.out.println(solve());
t--;
}
}
}
def solve(): FR, AR = "Friend", "Arnab" n, name = input().split() n = int(n) In = list(map(int,input().split())) st = name == "Nishant" if(n == 1): if In[0] % 2: return FR else: AR if(st == (n % 2 == 0)): return AR cnt = 0 for i in range(n): if(In[i] % 2): cnt += 1 i += 1 if(cnt >= (n + 1) // 2): return FR return AR for _ in range(int(input())): print(solve())
[forminator_quiz id="2343"]
So, in this blog, we have tried to explain the concept of Game Theory. If you want to solve more questions on Game Theory, which are curated by our expert mentors at PrepBytes, you can follow this link Game Theory.