Número de saltos de un ladrón para cruzar paredes

Un ladrón que intenta escapar de una cárcel. Tiene que cruzar N paredes, cada una con diferentes alturas (todas las alturas son mayores que 0). Sube X pies cada vez. Pero, debido a la naturaleza resbaladiza de esas paredes, cada vez que se desliza hacia atrás por Y pies. Ahora la tarea es calcular el número total de saltos necesarios para cruzar todas las paredes y escapar de la cárcel.
Ejemplos: 
 

Input : heights[] = {11, 11}
                X = 10;
                Y = 1; 
Output : 4
He needs to make 2 jumps for first wall
and 2 jumps for second wall.

Input : heights[] = {11, 10, 10, 9}
                 X = 10;
                 Y = 1;
Output : 5

La solución es bastante simple si la altura de la pared es menor o igual a x, solo se requiere un salto en esa pared; de lo contrario, podemos calcularlo por la altura de la pared-(subir-subir-bajar) y obtener los saltos requeridos. 
 

C++

// C++ program to find the number of
// jumps required
#include <iostream>
using namespace std;
 
/* function to calculate jumps required to cross
   walls */
int jumpcount(int x, int y, int n, int height[])
{
    int jumps = 0;
 
    for (int i = 0; i < n; i++) {
        if (height[i] <= x) {
            jumps++;
            continue;
        }
 
        /* If height of wall is greater than
           up move */
        int h = height[i];
        while (h > x)
        {
            jumps++;
            h = h - (x - y);
        }
        jumps++;
    }
    return jumps;
}
 
/*driver function*/
int main()
{
    int x = 10, y = 1;
    int height[] = { 11, 10, 10, 9 };
    int n = sizeof(height)/sizeof(height[0]);
    cout << jumpcount(x, y, n, height);
    return 0;
}

Java

// Java program to find the number of
// jumps required
public class GFG {
      
    /* function to calculate jumps required
         to cross walls */
    static int jumpcount(int x, int y, int n,
                                  int height[])
    {
        int jumps = 0;
      
        for (int i = 0; i < n; i++) {
            if (height[i] <= x) {
                jumps++;
                continue;
            }
      
            /* If height of wall is greater than
               up move */
            int h = height[i];
            while (h > x)
            {
                jumps++;
                h = h - (x - y);
            }
            jumps++;
        }
        return jumps;
    }
      
    /*driver function*/
    public static void main(String args[])
    {
        int x = 10, y = 1;
        int height[] = { 11, 10, 10, 9 };
        int n = height.length;
        System.out.println(jumpcount(x, y, n, height));
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python program to find the number of
# jumps required
 
# function to calculate jumps required to
# cross walls
def jumpcount(x, y, n, height):
    jumps = 0
  
    for i in range(n):
        if (height[i] <= x):
            jumps += 1
            continue
  
        """ If height of wall is greater than
           up move """
        h = height[i]
        while (h > x):
            jumps += 1
            h = h - (x - y)
        jumps += 1
    return jumps
  
# driver function
x = 10
y = 1
height = [ 11, 10, 10, 9 ]
n = len(height)
print (jumpcount(x, y, n, height))
 
# This code is contributed by Sachin Bisht

C#

// C# program to find the 
// number of jumps required
using System;
 
public class GFG {
     
    // function to calculate jumps 
    // required to cross walls
    static int jumpcount(int x, int y,
                         int n, int []height)
    {
        int jumps = 0;
     
        for (int i = 0; i < n; i++) {
            if (height[i] <= x) {
                jumps++;
                continue;
            }
     
            // If height of wall is 
            // greater than up move
            int h = height[i];
            while (h > x)
            {
                jumps++;
                h = h - (x - y);
            }
            jumps++;
        }
        return jumps;
    }
     
    // Driver Code
    public static void Main(String []args)
    {
        int x = 10, y = 1;
        int []height = {11, 10, 10, 9};
        int n = height.Length;
        Console.WriteLine(jumpcount(x, y, n, height));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find the
// number of jumps required
 
/* function to calculate
jumps required to cross walls */
function jumpcount($x, $y, $n,
                   $height)
{
    $jumps = 0;
 
    for ( $i = 0; $i < $n; $i++)
    {
        if ($height[$i] <= $x)
        {
            $jumps++;
            continue;
        }
 
        /* If height of wall is
        greater than up move */
        $h = $height[$i];
        while ($h > $x)
        {
            $jumps++;
            $h = $h - ($x - $y);
        }
        $jumps++;
    }
    return $jumps;
}
 
// Driver Code
$x = 10; $y = 1;
$height = array( 11, 10, 10, 9 );
$n = count($height);
echo jumpcount($x, $y, $n, $height);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
    // JavaScript program to find the
    // number of jumps required
     
    // function to calculate jumps 
    // required to cross walls
    function jumpcount(x, y, n, height)
    {
        let jumps = 0;
       
        for (let i = 0; i < n; i++) {
            if (height[i] <= x) {
                jumps++;
                continue;
            }
       
            // If height of wall is 
            // greater than up move
            let h = height[i];
            while (h > x)
            {
                jumps++;
                h = h - (x - y);
            }
            jumps++;
        }
        return jumps;
    }
     
    let x = 10, y = 1;
    let height = [11, 10, 10, 9];
    let n = height.length;
    document.write(jumpcount(x, y, n, height));
         
</script>

Producción:  

5

Complejidad de tiempo: O (altura [i] * n)

Espacio Auxiliar: O(1)

Podemos optimizar la solución anterior calculando directamente el número de saltos.
 

C++

// C++ program to find the number of
// jumps required
#include <iostream>
using namespace std;
 
/* function to calculate jumps required
   to cross  walls */
int jumpcount(int x, int y, int n, int height[])
{
    int jumps = 0;
    for (int i = 0; i < n; i++) {
 
        // Since all heights are
        // greater than 1, at-least
        // one jump is always required
        jumps++;
 
        // More jumps required if height
        // is greater than x.
        if (height[i] > x)
        {
           // Since we have already counted
           // one jump
           int h = height[i] - (x - y);
 
           // Remaining jumps
           jumps += h/(x - y);
 
           // If there was a remainder greater
           // than 1. 1 is there to handle cases
           // like x = 11, y = 1, height[i] = 21.
           if (h % (x-y) > 1)
             jumps++;
        }
    }
    return jumps;
}
 
/* driver function */
int main()
{
    int x = 10;
    int y = 1;
    int height[] = { 11, 34, 27, 9 };
    int n = sizeof(height)/sizeof(height[0]);
    cout << jumpcount(x, y, n, height);
    return 0;
}

Java

// Java program to find the number of
// jumps required
public class GFG {
      
      
    /* function to calculate jumps required
       to cross  walls */
    static int jumpcount(int x, int y, int n,
                                   int height[])
    {
        int jumps = 0;
        for (int i = 0; i < n; i++) {
      
            // Since all heights are
            // greater than 1, at-least
            // one jump is always required
            jumps++;
      
            // More jumps required if height
            // is greater than x.
            if (height[i] > x)
            {
               // Since we have already counted
               // one jump
               int h = height[i] - (x - y);
      
               // Remaining jumps
               jumps += h/(x - y);
      
               // If there was a remainder greater
               // than 1. 1 is there to handle cases
               // like x = 11, y = 1, height[i] = 21.
               if (h % (x-y) > 1)
                 jumps++;
            }
        }
        return jumps;
    }
      
    /* driver function */
    public static void main(String args[])
    {
        int x = 10;
        int y = 1;
        int height[] = { 11, 34, 27, 9 };
        int n = height.length;
        System.out.println(jumpcount(x, y, n, height));
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python program to find the number of
# jumps required
 
""" function to calculate jumps required
   to cross  walls """
def jumpcount(x, y, n, height):
    jumps = 0
    for i in range(n):
  
        # Since all heights are
        # greater than 1, at-least
        # one jump is always required
        jumps += 1
  
        # More jumps required if height
        # is greater than x.
        if (height[i] > x):
           
            # Since we have already counted
            # one jump
            h = height[i] - (x - y)
  
            # Remaining jumps
            jumps += h//(x - y)
  
            # If there was a remainder greater
            # than 1. 1 is there to handle cases
            # like x = 11, y = 1, height[i] = 21.
            if (h % (x-y) > 1):
                jumps += 1
    return jumps
  
# driver function
x = 10
y = 1
height = [ 11, 34, 27, 9 ]
n = len(height)
print (jumpcount(x, y, n, height))
 
# This code is contributed by Sachin Bisht

C#

// C# program to find the
// number of jumps required
using System;
 
public class GFG {
     
    // Function to calculate jumps
    // required to cross walls
    static int jumpcount(int x, int y,
                         int n, int []height)
   {
        int jumps = 0;
        for (int i = 0; i < n; i++) {
     
            // Since all heights are
            // greater than 1, at-least
            // one jump is always required
            jumps++;
     
            // More jumps required if
            // height is greater than x.
            if (height[i] > x)
            {
            // Since we have already
            // counted one jump
            int h = height[i] - (x - y);
     
            // Remaining jumps
            jumps += h / (x - y);
     
            // If there was a remainder greater
            // than 1. 1 is there to handle cases
            // like x = 11, y = 1, height[i] = 21.
            if (h % (x - y) > 1)
                jumps++;
            }
        }
        return jumps;
    }
     
    // Driver Code
    public static void Main(String []args)
    {
        int x = 10;
        int y = 1;
        int []height = {11, 34, 27, 9};
        int n = height.Length;
        Console.WriteLine(jumpcount(x, y, n, height));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find the
// number of jumps required
 
// function to calculate jumps
// required to cross walls
function jumpcount($x, $y,
                   $n, $height)
{
    $jumps = 0;
    for ($i = 0; $i < $n; $i++)
    {
 
        // Since all heights are
        // greater than 1, at-least
        // one jump is always required
        $jumps++;
 
        // More jumps required if height
        // is greater than x.
        if ($height[$i] > $x)
        {
             
            // Since we have
            // already counted
            // one jump
            $h = $height[$i] - ($x - $y);
     
            // Remaining jumps
            $jumps += $h / ($x - $y);
     
            // If there was a
            // remainder greater
            // than 1. 1 is there
            // to handle cases
            // like x = 11, y = 1,
            // height[i] = 21.
            if ($h % ($x - $y) > 1)
                $jumps++;
        }
    }
    return $jumps;
}
 
// Driver Code
{
    $x = 10;
    $y = 1;
    $height = array(11, 34, 27, 9);
    $n = sizeof($height) / sizeof($height[0]);
    echo jumpcount($x, $y, $n, $height);
    return 0;
}
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
    // Javascript program to find the number of jumps required
     
    // Function to calculate jumps
    // required to cross walls
    function jumpcount(x, y, n, height)
   {
        let jumps = 0;
        for (let i = 0; i < n; i++) {
       
            // Since all heights are
            // greater than 1, at-least
            // one jump is always required
            jumps++;
       
            // More jumps required if
            // height is greater than x.
            if (height[i] > x)
            {
            // Since we have already
            // counted one jump
            let h = height[i] - (x - y);
       
            // Remaining jumps
            jumps += parseInt(h / (x - y), 10);
       
            // If there was a remainder greater
            // than 1. 1 is there to handle cases
            // like x = 11, y = 1, height[i] = 21.
            if (h % (x - y) > 1)
                jumps++;
            }
        }
        return jumps;
    }
     
    let x = 10;
    let y = 1;
    let height = [11, 34, 27, 9];
    let n = height.length;
    document.write(jumpcount(x, y, n, height));
     
    // This code is contributed by mukesh07.
</script>

Producción: 

10

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Este artículo es una contribución de Pranav . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *