Dados N monstruos, cada monstruo tiene una salud inicial h[i], que es un número entero. Un monstruo está vivo si su salud es mayor que 0 . En cada turno, un monstruo aleatorio mata a otro monstruo aleatorio, el monstruo que es atacado, su salud se reduce por la cantidad de salud del monstruo atacante. Este proceso continúa hasta que queda un solo monstruo. ¿Cuál será la salud mínima posible del último monstruo que queda? En otras palabras, la tarea es jugar el juego de tal manera que el monstruo que queda al final tenga la menor salud posible.
Ejemplos:
Entrada: h[] = {2, 14, 28, 56}
Salida: 2
Cuando solo el primer monstruo continúa atacando a los 3 monstruos restantes, la salud final del último monstruo será 2, que es el mínimo.
Entrada: h[] = {7, 17, 9, 100, 25}
Salida: 1
Entrada: h[] = {5, 5, 5}
Salida: 5
Enfoque: se puede observar a partir del problema que uno tiene que encontrar un cierto valor de salud del monstruo, digamos k que puede matar a otros monstruos, incluido uno mismo. Una vez que se hace esta observación crucial, el problema se vuelve fácil. Supongamos que tenemos dos monstruos con salud h1 y h2 , y digamos h2 > h1 . Podemos ver que en una elección aleatoria, la forma óptima sería elegir un monstruo con menor salud y reducir la salud del otro monstruo hasta que su salud sea menor que la salud del monstruo atacante. Después de eso, elegiremos el segundo monstruo cuya salud sea inferior a h1 y el proceso continuará hasta que solo quede un monstruo. Así que al final nos quedaremos con el valor mínimo que seríamcd(h1, h2) . Este método gcd se puede extender para todos los monstruos.
Entonces, nuestra salud mínima posible resultante del monstruo será el mcd de toda la salud de los monstruos dados, es decir, H(min) = mcd(h1, h2, …, hn).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the gcd of two numbers
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return the minimum
// possible health for the monster
int solve(int* health, int n)
{
// gcd of first and second element
int currentgcd = gcd(health[0], health[1]);
// gcd for all subsequent elements
for (int i = 2; i < n; ++i) {
currentgcd = gcd(currentgcd, health[i]);
}
return currentgcd;
}
// Driver code
int main()
{
int health[] = { 4, 6, 8, 12 };
int n = sizeof(health) / sizeof(health[0]);
cout << solve(health, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the gcd of two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return the minimum
// possible health for the monster
static int solve(int health[], int n)
{
// gcd of first and second element
int currentgcd = gcd(health[0], health[1]);
// gcd for all subsequent elements
for (int i = 2; i < n; ++i)
{
currentgcd = gcd(currentgcd, health[i]);
}
return currentgcd;
}
// Driver code
public static void main(String args[])
{
int health[] = { 4, 6, 8, 12 };
int n = health.length;
System.out.println(solve(health, n));
}
}
// This code is contributed by
// Surendra_Gangwar
Python3
# Python3 implementation of the approach # Function to return the gcd of two numbers def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # Function to return the minimum # possible health for the monster def solve(health, n): # gcd of first and second element currentgcd = gcd(health[0], health[1]) # gcd for all subsequent elements for i in range(2, n): currentgcd = gcd(currentgcd, health[i]) return currentgcd # Driver code health = [4, 6, 8, 12] n = len(health) print(solve(health, n)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the gcd of two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return the minimum
// possible health for the monster
static int solve(int []health, int n)
{
// gcd of first and second element
int currentgcd = gcd(health[0], health[1]);
// gcd for all subsequent elements
for (int i = 2; i < n; ++i)
{
currentgcd = gcd(currentgcd, health[i]);
}
return currentgcd;
}
// Driver code
public static void Main(String []args)
{
int []health = { 4, 6, 8, 12 };
int n = health.Length;
Console.WriteLine(solve(health, n));
}
}
// This code is contributed by Arnab Kundu
PHP
<?php
// PHP implementation of the approach
// Function to return the gcd of two numbers
function gcd($a, $b)
{
if ($a == 0)
return $b;
return gcd($b % $a, $a);
}
// Function to return the minimum
// possible health for the monster
function solve($health, $n)
{
// gcd of first and second element
$currentgcd = gcd($health[0],
$health[1]);
// gcd for all subsequent elements
for ($i = 2; $i < $n; ++$i)
{
$currentgcd = gcd($currentgcd,
$health[$i]);
}
return $currentgcd;
}
// Driver code
$health = array(4, 6, 8, 12);
$n = sizeof($health);
echo solve($health, $n);
// This code is contributed by Akanksha Rai
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the gcd of two numbers
function gcd(a, b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return the minimum
// possible health for the monster
function solve(health, n)
{
// gcd of first and second element
let currentgcd = gcd(health[0], health[1]);
// gcd for all subsequent elements
for (let i = 2; i < n; ++i)
{
currentgcd = gcd(currentgcd, health[i]);
}
return currentgcd;
}
// Driver Code
let health = [ 4, 6, 8, 12 ];
let n = health.length;
document.write(solve(health, n));
// This code is contributed by target_2.
</script>
2
Complejidad de tiempo: O(N * log(MAX)) donde N es el tamaño de la array y MAX es el número máximo en la array.
Estamos ejecutando un ciclo que toma tiempo O(N). Además, la función GCD toma O(log(min(A, B)), y en el peor de los casos, cuando A y B son iguales y A = B = MAX, entonces la función GCD toma O(log(MAX)) tiempo. Por lo tanto, la complejidad del tiempo total = O(N * log(MAX))
Espacio auxiliar: O(log(MAX))