Encuentra la distancia máxima recorrida usando n bicicletas

Hay n bicicletas y cada una puede recorrer 100 km cuando está totalmente cargada. ¿Cuál es la distancia máxima que puede recorrer usando n bicicletas? Puede suponer que todas las bicicletas son similares y que una bicicleta necesita 1 litro para recorrer 1 km.
Tienes n bicicletas y usando una bicicleta solo puedes recorrer 100 km. por lo tanto, si n bicicletas comienzan desde el mismo punto y corren simultáneamente, solo puede recorrer 100 km. Pensemos un poco diferente, el truco es cuando quieres cubrir la distancia máxima, siempre debes intentar desperdiciar el mínimo de combustible. Desperdicio mínimo de combustible significa hacer funcionar un número mínimo de bicicletas. En lugar de correr en paralelo n bicicletas, puedes pensar en correrlas en serie. Eso significa que si transfiere cierta cantidad de combustible de la última bicicleta a otras bicicletas y arroja la última bicicleta, es decir, no haga funcionar la última bicicleta después de cierto punto. Pero la pregunta es, después de qué distancia se debe hacer la transferencia de combustible para que se cubra la distancia máxima y el tanque de combustible de las bicicletas restantes no se desborde. 
 

Tomemos los siguientes casos base y luego generalicemos la solución. 
 

• Caso base 1: hay una bicicleta: esto es simple, solo podemos cubrir 100 km.
• Caso base 2: Hay dos bicicletas: ¿ Cuál es la distancia máxima que podemos recorrer cuando hay 2 bicicletas? Para maximizar la distancia, debemos dejar caer la segunda bicicleta en algún punto y transferir su combustible a la primera bicicleta. Vamos a hacer el transbordo después de x kms.

Total distance covered = Distance covered by 100 ltr in first bike +  
                         Distance covered by fuel transferred from 
                         first bike. 

• El combustible restante en la segunda bicicleta es 100 – x. Si transferimos esta cantidad de combustible a la primera moto, la distancia total sería 100 + 100 – x, que es 200 – x. Así que nuestra tarea es maximizar 200-x. La restricción es, 100 – x debe ser menor o igual que el espacio creado en la primera bicicleta después de x km, es decir, 100 – x <= x. El valor de 200-x se vuelve máximo cuando x es mínimo. El mínimo valor posible de x es 50. Entonces somos capaces de viajar 150 kms. 
   
• Caso Base 3: Hay tres bicicletas: Deje que la primera transferencia se realice después de x kms. Después de x distancia, todas las bicicletas contienen 100-x cantidad de combustible. Si tomamos 100-x de la cantidad de combustible de la 3.ª bicicleta y la distribuimos entre la 1.ª y la 2.ª bicicleta para que se llenen los depósitos de combustible de la 1.ª y la 2.ª bicicleta. Entonces 100-x <= 2*x; o bien, x=33,333, por lo que debemos transferir el combustible restante de la tercera bicicleta y distribuir esa cantidad de combustible entre la 1.ª y la 2.ª bicicleta después de exactamente 33,33 km.

Generalicemos. Si observamos más de cerca los casos anteriores, podemos observar que si hay n bicicletas, la primera transferencia se realiza (o se deja caer una bicicleta) después de 100/n km. Para generalizar más, cuando tenemos x litros de combustible restante en cada bicicleta y n bicicletas restantes, dejamos caer una bicicleta después de x/n kms.

A continuación se muestra la implementación de una función general. 

#include <stdio.h>
 
// Returns maximum distance that can be traveled by n bikes and given fuel
// in every bike
double maxDistance(int n, int fuel)
{
    // dist_covered is the result of this function
    double dist_covered = 0;
 
    while (n > 0)
    {
        // after ever fuel/n km we are discarding one bike and filling
        // all the other bikes with fuel/n liters of fuel i.e. to their
        // maximum limit (100 litre)
 
        dist_covered += (double)fuel / n;
 
        n -= 1; // reduce number of bikes
    }
    return dist_covered;
}
 
// Driver program to test above function
int main()
{
    int n = 3; // number of bikes
    int fuel = 100;
    printf("Maximum distance possible with %d bikes is %f",
            n, maxDistance(n, fuel));
    return 0;
}

// Java program to find the maximum
// distance covered using n bikes
import java.io.*;
 
class GFG
{
    // Function that returns maximum distance that can be traveled by n bikes
    // and given fuel in every bike
    static double maxDistance(int n, int fuel)
    {
         // dist_covered is the result of this function
        double dist_covered = 0;
  
        while (n > 0)
        {
            // after ever fuel/n km we are discarding one bike and filling
            // all the other bikes with fuel/n liters of fuel i.e. to their
            // maximum limit (100 litre)
  
            dist_covered += (double)fuel / n;
  
            n -= 1;  // reduce number of bikes
        }
        return dist_covered;
    }
     
    // driver program
    public static void main (String[] args)
    {
        int n = 3; // number of bikes
        int fuel = 100;
        System.out.println("Maximum distance possible with "
                                   + n + " bikes is " + maxDistance(n, fuel));
    }
}
 
// Contributed by Pramod Kumar

# Python 3 program to find the maximum
# distance covered using n bikes
 
# Returns maximum distance that can be
# traveled by n bikes and given fuel
# in every bike
def maxDistance(n, fuel):
     
    # dist_covered is the result
    # of this function
    dist_covered = 0
 
    while (n > 0):
         
        # after ever fuel/n km we are
        # discarding one bike and filling
        # all the other bikes with fuel/n
        # liters of fuel i.e. to their
        # maximum limit (100 litre)
        dist_covered = dist_covered + (fuel / n)
         
        # reduce number of bikes
        n = n - 1
 
    return dist_covered
 
# Driver Code
if __name__ =='__main__':
    n = 3
     
    # number of bikes
    fuel = 100
    print("Maximum distance possible with",
       n, "bikes is", maxDistance(n, fuel))
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find the maximum
// distance covered using n bikes
using System;
 
class GFG {
 
    // Function that returns maximum distance
    // that can be travelled by n bikes
    // and given fuel in every bike
    static double maxDistance(int n, int fuel)
    {
        // dist_covered is the result of this function
        double dist_covered = 0;
 
        while (n > 0) {
             
            // after ever fuel/n km we are discarding
            // one bike and filling all the other bikes
            // with fuel/n liters of fuel i.e. to their
            // maximum limit (100 litre)
            dist_covered += (double)fuel / n;
 
            n -= 1; // reduce number of bikes
        }
        return dist_covered;
    }
 
    // driver program
    public static void Main()
    {
        // number of bikes
        int n = 3;
        int fuel = 100;
        Console.WriteLine("Maximum distance possible with " + n +
                          " bikes is " + maxDistance(n, fuel));
    }
}
 
// This code is contributed by Sam007

<?php
// Returns maximum distance that can
// be traveled by n bikes and given
// fuel in every bike
 
function maxDistance($n, $fuel)
{
    // dist_covered is the result
    // of this function
    $dist_covered = 0;
 
    while ($n > 0)
    {
        // after ever fuel/n km we are
        // discarding one bike and filling
        // all the other bikes with fuel/n
        // liters of fuel i.e. to their
        // maximum limit (100 litre)
 
        $dist_covered += (double)$fuel / $n;
 
        // reduce number of bikes
        $n -= 1;
    }
    return $dist_covered;
}
 
// Driver Code
 
// number of bikes
$n = 3;
$fuel = 100;
echo "Maximum distance possible with ",
                      $n, " bikes is ",
                maxDistance($n, $fuel);
 
// This code is contributed by ajit
?>

<script>
 
// Javascript program to find the maximum
// distance covered using n bikes
 
// Function that returns maximum distance
// that can be travelled by n bikes
// and given fuel in every bike
function maxDistance(n, fuel)
{
     
    // dist_covered is the result of this function
    let dist_covered = 0;
 
    while (n > 0)
    {
         
        // After ever fuel/n km we are discarding
        // one bike and filling all the other bikes
        // with fuel/n liters of fuel i.e. to their
        // maximum limit (100 litre)
        dist_covered += fuel / n;
         
        // Reduce number of bikes
        n -= 1;
    }
    return dist_covered.toFixed(6);
}
 
// Driver code
 
// Number of bikes
let n = 3;
let fuel = 100;
 
document.write("Maximum distance possible with " + n +
               " bikes is " + maxDistance(n, fuel));
                
// This code is contributed by divyesh072019
 
</script>

Producción : 

Maximum distance possible with 3 bikes is 183.333333

Complejidad de tiempo: O(N)
Espacio auxiliar: O(1)
 
Este artículo es una contribución de Shamik Mitra . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.