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.

Learn programming languages online and 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;
}

Previous post Longest Palindromic Substring
Next post Nearest Cell(paid)

Leave a Reply

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