Dados 4 enteros X, Y, A, B . En un movimiento, disminuya X en A e Y en B o disminuya X en B e Y en A . Calcular los movimientos máximos posibles. Dados 4 enteros X, Y, A, B . En un movimiento podemos hacer que X = X – A y Y = Y – B o X = X – B y Y = Y – A. Calcula el máximo total de movimientos posibles.
Ejemplo:
Entrada: X = 10, Y = 12, A = 2, B = 5
Salida: 3
Explicación : 1er movimiento: X = 8, Y = 7 después de restar X por A e Y por B
2do movimiento: X = 6, Y = 2 después de restar X por A e Y por B
3er movimiento: X = 1, Y = 0 después de restar X por B e Y por A
Entonces se pueden realizar un total de 3 movimientos.Entrada: X = 1, Y = 1, A = 2, B = 2
Salida: 0
Enfoque ingenuo: en cada valor de X e Y podemos restar el máximo de A y B del máximo de X e Y y restar el mínimo de A y B del mínimo de X e Y hasta que X e Y permanezcan mayores que cero.
Enfoque eficiente: el problema dado se puede resolver utilizando la técnica de búsqueda binaria en la respuesta.
- La idea clave aquí es que si para cualquier número de movimientos N es posible realizar tantos movimientos, entonces también podemos realizar N – 1 movimientos.
- Entonces podemos hacer una búsqueda binaria sobre la respuesta. Fije el rango L = 1 y R = 10000000 (Cambie esto si hay valores enteros grandes) y para cada valor mid = ( L + R )/2 verifique si podemos realizar tantos movimientos. Si es posible, cambie L = mid + 1, de lo contrario R = mid – 1. Devuelva el valor máximo posible.
- Para verificar cualquier número a la mitad, tenemos que disminuir X e Y al menos a la mitad * min( A , B ) y para el elemento restante, podemos calcular los valores totales restantes para | A – B |. Si estos valores son mayores que la mitad, aumente nuestro rango derecho; de lo contrario, disminuya el rango izquierdo.
Implementación:
C++
// C++ Program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Helper function to check if
// we can perform Mid number of moves
#define MAXN 10000000 // MAXN = 1e7
bool can(int Mid, int X, int Y, int A, int B)
{
// Remove atleast Mid * B from both X and Y
int p1 = X - Mid * B;
int p2 = Y - Mid * B;
// If any value is negative return false.
if (p1 < 0 || p2 < 0) {
return false;
}
// Calculate remaining values
int k = A - B;
if (k == 0) {
return true;
}
int val = p1 / k + p2 / k;
// If val >= Mid then it is possible
// to perform this much moves
if (val >= Mid) {
return true;
}
// else return false
return false;
}
int maxPossibleMoves(int X, int Y, int A, int B)
{
// Initialize a variable to store the answer
int ans = 0;
// Fix the left and right range
int L = 1, R = MAXN;
// Binary Search over the answer
while (L <= R) {
// Check for the middle
// value as the answer
int Mid = (L + R) / 2;
if (can(Mid, X, Y, A, B)) {
// It is possible to perform
// this much moves
L = Mid + 1;
// Maximise the answer
ans = max(ans, Mid);
}
else {
R = Mid - 1;
}
}
// Return answer
return ans;
}
// Driver Code
int main()
{
int X = 10, Y = 12, A = 2, B = 5;
// Generalise that A >= B
if (A < B) {
swap(A, B);
}
cout << maxPossibleMoves(X, Y, A, B);
}
Java
// Java program to implement the above approach
import java.io.*;
class GFG{
// Helper function to check if
// we can perform Mid number of moves
static int MAXN = 10000000;
static boolean can(int Mid, int X, int Y,
int A, int B)
{
// Remove atleast Mid * B from both X and Y
int p1 = X - Mid * B;
int p2 = Y - Mid * B;
// If any value is negative return false.
if (p1 < 0 || p2 < 0)
{
return false;
}
// Calculate remaining values
int k = A - B;
if (k == 0)
{
return true;
}
int val = p1 / k + p2 / k;
// If val >= Mid then it is possible
// to perform this much moves
if (val >= Mid)
{
return true;
}
// Else return false
return false;
}
static int maxPossibleMoves(int X, int Y, int A, int B)
{
// Initialize a variable to store the answer
int ans = 0;
// Fix the left and right range
int L = 1, R = MAXN;
// Binary Search over the answer
while (L <= R)
{
// Check for the middle
// value as the answer
int Mid = (L + R) / 2;
if (can(Mid, X, Y, A, B))
{
// It is possible to perform
// this much moves
L = Mid + 1;
// Maximise the answer
ans = Math.max(ans, Mid);
}
else
{
R = Mid - 1;
}
}
// Return answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
int X = 10, Y = 12, A = 2, B = 5;
// Generalise that A >= B
if (A < B)
{
int temp = A;
A = B;
B = temp;
}
System.out.println(maxPossibleMoves(X, Y, A, B));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python Program to implement the above approach # Helper function to check if # we can perform Mid number of moves MAXN = 10000000 def can(Mid, X, Y, A, B): # Remove atleast Mid * B from both X and Y p1 = X - Mid * B p2 = Y - Mid * B # If any value is negative return false. if (p1 < 0 or p2 < 0): return False # Calculate remaining values k = A - B if (k == 0): return True val = p1 // k + p2 // k # If val >= Mid then it is possible # to perform this much moves if (val >= Mid): return True # else return false return False def maxPossibleMoves(X, Y, A, B): # Initialize a variable to store the answer ans = 0 # Fix the left and right range L = 1 R = MAXN # Binary Search over the answer while (L <= R): # Check for the middle # value as the answer Mid = (L + R) // 2 if (can(Mid, X, Y, A, B)): # It is possible to perform # this much moves L = Mid + 1 # Maximise the answer ans = max(ans, Mid) else: R = Mid - 1 # Return answer return ans # Driver Code X = 10 Y = 12 A = 2 B = 5 # Generalise that A >= B if (A < B): tmp = A A = B B = tmp print(maxPossibleMoves(X, Y, A, B)) # This code is contributed by shivanisinghss2110
C#
// C# program to implement the above approach
using System;
class GFG{
// Helper function to check if
// we can perform Mid number of moves
static int MAXN = 10000000;
static Boolean can(int Mid, int X, int Y,
int A, int B)
{
// Remove atleast Mid * B from both X and Y
int p1 = X - Mid * B;
int p2 = Y - Mid * B;
// If any value is negative return false.
if (p1 < 0 || p2 < 0)
{
return false;
}
// Calculate remaining values
int k = A - B;
if (k == 0)
{
return true;
}
int val = p1 / k + p2 / k;
// If val >= Mid then it is possible
// to perform this much moves
if (val >= Mid)
{
return true;
}
// Else return false
return false;
}
static int maxPossibleMoves(int X, int Y, int A, int B)
{
// Initialize a variable to store the answer
int ans = 0;
// Fix the left and right range
int L = 1, R = MAXN;
// Binary Search over the answer
while (L <= R)
{
// Check for the middle
// value as the answer
int Mid = (L + R) / 2;
if (can(Mid, X, Y, A, B))
{
// It is possible to perform
// this much moves
L = Mid + 1;
// Maximise the answer
ans = Math.Max(ans, Mid);
}
else
{
R = Mid - 1;
}
}
// Return answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int X = 10, Y = 12, A = 2, B = 5;
// Generalise that A >= B
if (A < B)
{
int temp = A;
A = B;
B = temp;
}
Console.Write(maxPossibleMoves(X, Y, A, B));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript Program to implement the above approach
// Helper function to check if
// we can perform Mid number of moves
let MAXN = 10000000; // MAXN = 1e7
function can(Mid, X, Y, A, B)
{
// Remove atleast Mid * B from both X and Y
let p1 = X - Mid * B;
let p2 = Y - Mid * B;
// If any value is negative return false.
if (p1 < 0 || p2 < 0) {
return false;
}
// Calculate remaining values
let k = A - B;
if (k == 0) {
return true;
}
let val = Math.floor(p1 / k) + Math.floor(p2 / k);
// If val >= Mid then it is possible
// to perform this much moves
if (val >= Mid) {
return true;
}
// else return false
return false;
}
function maxPossibleMoves(X, Y, A, B)
{
// Initialize a variable to store the answer
let ans = 0;
// Fix the left and right range
let L = 1,
R = MAXN;
// Binary Search over the answer
while (L <= R)
{
// Check for the middle
// value as the answer
let Mid = Math.floor((L + R) / 2);
if (can(Mid, X, Y, A, B))
{
// It is possible to perform
// this much moves
L = Mid + 1;
// Maximise the answer
ans = Math.max(ans, Mid);
} else {
R = Mid - 1;
}
}
// Return answer
return ans;
}
// Driver Code
let X = 10,
Y = 12,
A = 2,
B = 5;
// Generalise that A >= B
if (A < B) {
let temp = A;
A = B;
B = temp;
}
document.write(maxPossibleMoves(X, Y, A, B));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
3
Complejidad de tiempo: O(log(MAXN)), donde MAXN es el número máximo de movimientos
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA