Play Games 3

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
Friend

OBSERVATION:

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;
}

[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.

Leave a Reply

Your email address will not be published. Required fields are marked *