Dados números A de bolas blancas y números B de bolas negras. Necesitas tener X cantidad de bolas blancas e Y cantidad de bolas negras (A <= X, B <= Y) para ganar el juego haciendo algunas operaciones (cero o más).
En una operación : En cualquier momento si tienes p bolas blancas y q negras entonces en ese momento puedes comprar q bolas blancas o p negras.
Encuentra si es posible tener X bolas blancas e Y negras al final o no.
Ejemplos:
Input: A = 1, B = 1, X = 3, Y = 8 Output: POSSIBLE Explanation: The steps are, (1, 1)->(1, 2)->(3, 2)->(3, 5)->(3, 8) Input: A = 3, Y = 2, X = 4, Y = 6 Output: NOT POSSIBLE
Enfoque:
Tenemos que resolver este problema usando la propiedad de mcd. Veamos cómo.
- Inicialmente, tenemos una bola blanca y una bola negra B. Tenemos que conseguir el resto de las bolas rojas XA y las bolas negras YB.
- A continuación se muestra la propiedad de mcd de dos números que usaremos,
gcd(x, y) = gcd(x + y, y) gcd(x, y) = gcd(x, y + x)
- Esta propiedad es la misma que la operación que se menciona en la pregunta. Entonces, a partir de aquí, obtenemos que si el mcd del estado final es el mismo que el mcd del estado inicial, siempre es posible alcanzar la meta, de lo contrario no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Find is it possible
// to have X white and Y black
// balls at the end.
#include <bits/stdc++.h>
using namespace std;
// Recursive function to return
// gcd of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function returns if it's
// possible to have X white
// and Y black balls or not.
void IsPossible(int a, int b,
int x, int y)
{
// Finding gcd of (x, y)
// and (a, b)
int final = gcd(x, y);
int initial = gcd(a, b);
// If gcd is same, it's always
// possible to reach (x, y)
if (initial == final)
{
cout << "POSSIBLE\n";
}
else
{
// Here it's never possible
// if gcd is not same
cout << "NOT POSSIBLE\n";
}
}
// Driver Code
int main()
{
int A = 1, B = 2, X = 4, Y = 11;
IsPossible(A, B, X, Y);
A = 2, B = 2, X = 3, Y = 6;
IsPossible(A, B, X, Y);
return 0;
}
Java
// Java program to Find is it possible
// to have X white and Y black
// balls at the end.
import java.io.*;
class GFG{
// Recursive function to return
// gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function returns if it's
// possible to have X white
// and Y black balls or not.
static void IsPossible(int a, int b,
int x, int y)
{
// Finding gcd of (x, y)
// and (a, b)
int g = gcd(x, y);
int initial = gcd(a, b);
// If gcd is same, it's always
// possible to reach (x, y)
if (initial == g)
{
System.out.print("POSSIBLE\n");
}
else
{
// Here it's never possible
// if gcd is not same
System.out.print("NOT POSSIBLE\n");
}
}
// Driver code
public static void main(String args[])
{
int A = 1, B = 2, X = 4, Y = 11;
IsPossible(A, B, X, Y);
A = 2; B = 2; X = 3; Y = 6;
IsPossible(A, B, X, Y);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program to find is it possible
# to have X white and Y black
# balls at the end.
# Recursive function to return
# gcd of a and b
def gcd(a, b) :
if (b == 0) :
return a;
return gcd(b, a % b);
# Function returns if it's
# possible to have X white
# and Y black balls or not.
def IsPossible(a, b, x, y) :
# Finding gcd of (x, y)
# and (a, b)
final = gcd(x, y);
initial = gcd(a, b);
# If gcd is same, it's always
# possible to reach (x, y)
if (initial == final) :
print("POSSIBLE");
else :
# Here it's never possible
# if gcd is not same
print("NOT POSSIBLE");
# Driver Code
if __name__ == "__main__" :
A = 1; B = 2; X = 4; Y = 11;
IsPossible(A, B, X, Y);
A = 2; B = 2; X = 3; Y = 6;
IsPossible(A, B, X, Y);
# This code is contributed by AnkitRai01
C#
// C# program to Find is it possible
// to have X white and Y black
// balls at the end.
using System;
using System.Linq;
class GFG {
// Recursive function to return
// gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function returns if it's
// possible to have X white
// and Y black balls or not.
static void IsPossible(int a, int b,
int x, int y)
{
// Finding gcd of (x, y)
// and (a, b)
int g = gcd(x, y);
int initial = gcd(a, b);
// If gcd is same, it's always
// possible to reach (x, y)
if (initial == g)
{
Console.Write("POSSIBLE\n");
}
else
{
// Here it's never possible
// if gcd is not same
Console.Write("NOT POSSIBLE\n");
}
}
// Driver code
static public void Main()
{
int A = 1, B = 2;
int X = 4, Y = 11;
IsPossible(A, B, X, Y);
A = 2; B = 2;
X = 3; Y = 6;
IsPossible(A, B, X, Y);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program to Find is it possible
// to have X white and Y black
// balls at the end.
// Recursive function to return
// gcd of a and b
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function returns if it's
// possible to have X white
// and Y black balls or not.
function IsPossible(a, b, x, y)
{
// Finding gcd of (x, y)
// and (a, b)
let final = gcd(x, y);
let initial = gcd(a, b);
// If gcd is same, it's always
// possible to reach (x, y)
if (initial == final)
{
document.write("POSSIBLE" + "</br>");
}
else
{
// Here it's never possible
// if gcd is not same
document.write("NOT POSSIBLE" + "</br>");
}
}
let A = 1, B = 2, X = 4, Y = 11;
IsPossible(A, B, X, Y);
A = 2, B = 2, X = 3, Y = 6;
IsPossible(A, B, X, Y);
// This code is contributed by divyesh072019.
</script>
Producción:
POSSIBLE NOT POSSIBLE
Complejidad del tiempo: O(log(max(A, B, X, Y)))
Espacio Auxiliar: O(1)