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