Horje
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));

Output

B
A

Time Complexity: O(1)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Modify shortest distance between source and destination to K Modify shortest distance between source and destination to K
Minimum number of keypresses to type the given string Minimum number of keypresses to type the given string
Maximize unique elements in set after K deletions from each array Maximize unique elements in set after K deletions from each array
Which is the best YouTube channel to Learn DSA? Which is the best YouTube channel to Learn DSA?
Is Data Structures and Algorithms Required for Android Development? Is Data Structures and Algorithms Required for Android Development?

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje