Given a grid on the XY plane with dimensions r x c (where r denotes maximum cells along the X axis and c denotes maximum cells along the Y axis), the two players (say JON and ARYA ) can move the coin over the grid satisfying the following rules:
- There is a coin on (1, 1) cell initially.
- JON will move first.
- Both will play on alternate moves.
- In each move, they can place the coin in the following positions if the current position of the coin is x, y
- (x+1, y), (x+2, y), (x+3, y), (x, y+1), (x, y+2), (x, y+3), (x, y+4), (x, y+5), (x, y+6)
- They can’t go outside the grid.
- Player who cannot make any move will lose this game.
- Both play optimally.
Examples:
Input: r = 1, c = 2
Output: JON
Explanation: ARYA lost the game because
he won’t able to move after JON’s move.Input: r = 2, c = 2
Output: ARYA
Explanation: After first move by JON (1, 2 or 2, 1)
and second move by ARYA(2, 2) JON won’t able to
move so ARYA wins.
Approach: This problem can be solved using game theory based on the following idea:
Check the following points:
- For rows whoever leaves 4 cells to be covered wins the game and for columns, whoever leaves 7 cells to be covered, wins the game.
- To win the game one has to make sure that the opponent cannot win either row or column i.e. he can win both the row and column and leaves 4 cells in row and 7 cells in columns.
- The game starts with Jon. So if (r-1)%7 = (c-1)%4, then Jon can win either row or column but not both. So Arya wins that game.
- In all other cases Jon wins the game.
Follow the steps to solve the problem:
- Get the value of (r-1)%7 and (c-1)%4.
- If these two values are the same, then Arya wins.
- Otherwise, Jon wins.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the winnerstring moveOnGrid(int r, int c){ r = (r - 1) % 7; c = (c - 1) % 4; if (r != c) return "JON"; return "ARYA";}// Driver codeint main(){ int r = 2, c = 2; // Function call cout << moveOnGrid(r, c); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG{ // Function to find the winner public static String moveOnGrid(int r, int c) { r = (r - 1) % 7; c = (c - 1) % 4; if (r != c) return "JON"; return "ARYA"; } // Driver Code public static void main(String[] args) { int r = 2, c = 2; // Function call System.out.print(moveOnGrid(r, c)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach# Function to find the winnerdef moveOnGrid(r, c): r = (r - 1) % 7 c = (c - 1) % 4 if (r != c): return "JON" return "ARYA"# Driver coder,c = 2,2# Function callprint(moveOnGrid(r, c))# This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;class GFG { // Function to find the winner public static String moveOnGrid(int r, int c) { r = (r - 1) % 7; c = (c - 1) % 4; if (r != c) return "JON"; return "ARYA"; } // Driver Code public static void Main () { int r = 2, c = 2; // Function call Console.Write(moveOnGrid(r, c)); }}// This code is contributed by jana_sayantan. |
Javascript
<script>// JavaScript code to implement the approach// Function to find the winnerfunction moveOnGrid(r, c){ r = (r - 1) % 7; c = (c - 1) % 4; if (r != c) return "JON"; return "ARYA";}// Driver codelet r = 2, c = 2;// Function calldocument.write(moveOnGrid(r, c));// This code is contributed by shinjanpatra</script> |
Output
ARYA
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
