Find the winner by incrementing co-ordinates till Euclidean distance <= D
A and B play a game and A starts first. Consider a Token placed at (0,0) in a 2D plane, a player can perform the below moves on the token:
- increase x coordinate of the token to x+K
- increase y coordinate of the token to y+K
After each move the euclidean distance of the token from origin should be smaller than equal to D. i.e. x2 + y2 <= D2 . The player who is unable to make a move looses.
Examples:
Input: D=2, K=1
Output: B
Explanation: From the initial position (0,0), player A has the option to move to either (0,1) or (1,0) From there, player B can move to any of the following coordinates: (0,2), (2,0) or (1,1). Now A cannot make any move. Therefore, B wins.Input: D=5, K=2
Output: A
Explanation: From the initial position (0,0), player A has the option to move to either (0,2) or (2,0). From there, player B can move to any of the following coordinates: (0,4), (2,2) or (4,0). Player A can only move to the coordinates: (4,2) or (2,4). Now B can not make any move. Therefore, A wins.
Approach: To solve the problem, follow the idea below:
The idea is to find the numbers of steps taken by both the players mathematically. Both players, A and B, move a distance of K. Since player A starts the game, the optimal strategy for player B is to maintain the trajectory on the line (y=x). This means that if player A moves K distance along the x-axis, player B will move K distance along the y-axis, and vice versa. This movement forms the hypotenuse of a triangle, with value √ 2 K.
The total distance to be covered is D, so the total number of hypotenuses formed will be D/√ 2 K. Since each hypotenuse is contributed by both players, the total number of steps becomes 2*D/√ 2 K = √ (2*(D2/K2)).
If the total number of steps is odd, player A wins. If it’s even, player B wins.
Step-by-step algorithm:
- Calculate the square of the maximum distance D that can be moved from the origin, divide it by the square of the step size K, and multiply the result by 2.
- Take the square root of the result which is the maximum number of steps that can be taken by both players combined.
- If the maximum number of steps is odd, player A wins. If it is even, player B wins.
Below is the implementation of the above algorithm:
C++
// C++ Code #include <bits/stdc++.h> using namespace std; // Function to determine the winner of the game string game( long long D, long long K) { // Calculate the square of the maximum distance D, // divide it by the square of the step size K, // and multiply the result by 2. long long x = 2 * ((D * D) / (K * K)); // Take the square root of the result // If the maximum number of steps is odd, // player A wins else player B wins. return ( int ( sqrt (x)) & 1 ? "A" : "B" ); } // Driver code int main() { // Test Case 1 long long D = 2, K = 1; cout << game(D, K) << endl; // Test Case 2 D = 5, K = 2; cout << game(D, K) << endl; return 0; } |
Java
// Java code import java.util.*; public class GFG { // Function to determine the winner of the game public static String game( long D, long K) { // Calculate the square of the maximum distance D, // divide it by the square of the step size K, // and multiply the result by 2. long x = 2 * ((D * D) / (K * K)); // Take the square root of the result // If the maximum number of steps is odd, // player A wins else player B wins. return (( int )Math.sqrt(x) & 1 ) == 1 ? "A" : "B"; } // Driver code public static void main(String[] args) { // Test Case 1 long D = 2 , K = 1 ; System.out.println(game(D, K)); // Test Case 2 D = 5 ; K = 2 ; System.out.println(game(D, K)); } } |
Python3
# Python code import math # Function to determine the winner of the game def game(D, K): # Calculate the square of the maximum distance D, # divide it by the square of the step size K, # and multiply the result by 2. x = 2 * ((D * D) / (K * K)) # Take the square root of the result # If the maximum number of steps is odd, # player A wins else player B wins. return 'A' if int (math.sqrt(x)) & 1 else 'B' # Driver code if __name__ = = "__main__": # Test Case 1 D = 2 K = 1 print (game(D, K)) # Test Case 2 D = 5 K = 2 print (game(D, K)) |
C#
using System; class Program { // Function to determine the winner of the game static string Game( long D, long K) { // Calculate the square of the maximum distance D, // divide it by the square of the step size K, // and multiply the result by 2. long x = 2 * ((D * D) / (K * K)); // Take the square root of the result // If the integer part of the square root is odd, // player A wins; else, player B wins. return (( long )Math.Sqrt(x) % 2 == 1) ? "A" : "B" ; } // Driver code static void Main() { // Test Case 1 long D1 = 2, K1 = 1; Console.WriteLine(Game(D1, K1)); // Test Case 2 long D2 = 5, K2 = 2; Console.WriteLine(Game(D2, K2)); } } // This code is contributed by akshitaguprzj3 |
Javascript
// Function to determine the winner of the game function game(D, K) { // Calculate the square of the maximum distance D, // divide it by the square of the step size K, // and multiply the result by 2. const x = 2 * Math.floor((D * D) / (K * K)); // Take the square root of the result // If the maximum number of steps is odd, // player A wins else player B wins. return Math.sqrt(x) % 2 === 1 ? "A" : "B" ; } // Test Case 1 let D = 2, K = 1; console.log(game(D, K)); // Test Case 2 D = 5, K = 2; console.log(game(D, K)); |
B A
Time Complexity: O(1)
Auxiliary Space: O(1)