Dados tres números enteros N , K y M que representan el Número de casillas (alineadas horizontalmente de 1 a N ), el número total de saltos permitidos y el total de monedas disponibles respectivamente, la tarea es imprimir el camino que se puede recorrer dentro de [1, N] usando exactamente M monedas en exactamente K saltos. Si se realiza un salto desde la posición X a la posición Y , se utilizan monedas abs(X – Y) . Si no es posible usar M monedas en K saltos, imprima -1.
Ejemplos:
Entrada: N = 5, K = 4, M = 12
Salida: 5 1 4 5
Explicación:
Primer salto: Caja 1 -> Caja 5. Por lo tanto, |1-5| = 4 monedas usadas.
Segundo Salto: Caja 5 -> Caja 1 Por lo tanto, |5-1| = 4 monedas usadas.
Tercer Salto: Caja 1 -> Caja 4 usando 3 monedas.
Cuarto Salto: Caja 4 -> Caja 5 usando 1 moneda.
Por lo tanto, se usaron exactamente 12 monedas en 4 saltos.
Entrada: N = 4, K = 3, M = 10
Salida: -1
Acercarse:
Podemos observar que la respuesta será -1 para los siguientes dos casos:
- K > N-1 o
- K * (N-1) < METRO .
El problema se puede resolver utilizando el enfoque codicioso siguiendo los pasos que se indican a continuación:
Repita la operación a continuación hasta que K se convierta en cero.
- Encuentra el mínimo de N-1 y M – K – 1 .
- Según el valor mínimo anterior, muévase hacia la izquierda o hacia la derecha según la disponibilidad, reduzca K.
- Repita los pasos anteriores hasta que K se convierta en 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print
// the path using exactly
// K jumps and M coins
#include <bits/stdc++.h>
using namespace std;
// Function that print the path
// using exactly K jumps and M coins
void print_path(int N, int jump, int coin)
{
// If no path exists
if (jump > coin
|| jump * (N - 1) < coin) {
cout << "-1" << endl;
}
else {
int pos = 1;
while (jump > 0) {
// It decides which
// box to be jump
int tmp = min(N - 1,
coin - (jump - 1));
// It decides whether
// to jump on left side or
// to jump on right side
if (pos + tmp <= N) {
pos += tmp;
}
else {
pos -= tmp;
}
// Print the path
cout << pos << " ";
coin -= tmp;
jump -= 1;
}
}
}
// Driver Code
int main()
{
int N = 5, K = 4, M = 12;
// Function Call
print_path(N, K, M);
return 0;
}
Java
// Java program to print the path
// using exactly K jumps and M coins
import java.io.*;
class GFG{
// Function that print the path
// using exactly K jumps and M coins
static void print_path(int N, int jump,
int coin)
{
// If no path exists
if (jump > coin || jump * (N - 1) < coin)
{
System.out.println("-1");
}
else
{
int pos = 1;
while (jump > 0)
{
// It decides which
// box to be jump
int tmp = Math.min(N - 1,
coin - (jump - 1));
// It decides whether
// to jump on left side or
// to jump on right side
if (pos + tmp <= N)
{
pos += tmp;
}
else
{
pos -= tmp;
}
// Print the path
System.out.print(pos + " ");;
coin -= tmp;
jump -= 1;
}
}
}
// Driver Code
public static void main (String[] args)
{
int N = 5, K = 4, M = 12;
// Function Call
print_path(N, K, M);
}
}
// This code is contributed by shubhamsingh10
Python3
# Python3 program to print the path
# using exactly K jumps and M coins
# Function that pr the path
# using exactly K jumps and M coins
def print_path(N, jump, coin):
# If no path exists
if (jump > coin or
jump * (N - 1) < coin):
print("-1")
else:
pos = 1;
while (jump > 0):
# It decides which
# box to be jump
tmp = min(N - 1,
coin - (jump - 1));
# It decides whether
# to jump on left side or
# to jump on right side
if (pos + tmp <= N):
pos += tmp;
else:
pos -= tmp;
# Print the path
print(pos, end = " ")
coin -= tmp;
jump -= 1;
# Driver code
N = 5
K = 4
M = 12
# Function call
print_path(N, K, M);
# This code is contributed by grand_master
C#
// C# program to print the path
// using exactly K jumps and M coins
using System;
class GFG{
// Function that print the path
// using exactly K jumps and M coins
static void print_path(int N, int jump,
int coin)
{
// If no path exists
if (jump > coin || jump * (N - 1) < coin)
{
Console.WriteLine("-1");
}
else
{
int pos = 1;
while (jump > 0)
{
// It decides which
// box to be jump
int tmp = Math.Min(N - 1,
coin - (jump - 1));
// It decides whether
// to jump on left side or
// to jump on right side
if (pos + tmp <= N)
{
pos += tmp;
}
else
{
pos -= tmp;
}
// Print the path
Console.Write(pos + " ");
coin -= tmp;
jump -= 1;
}
}
}
// Driver Code
public static void Main(String[] args)
{
int N = 5, K = 4, M = 12;
// Function Call
print_path(N, K, M);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to print the path
// using exactly K jumps and M coins
// Function that print the path
// using exactly K jumps and M coins
function print_path(N, jump, coin)
{
// If no path exists
if (jump > coin || jump * (N - 1) < coin)
{
document.write("-1");
}
else
{
let pos = 1;
while (jump > 0)
{
// It decides which
// box to be jump
let tmp = Math.min(N - 1,
coin - (jump - 1));
// It decides whether
// to jump on left side or
// to jump on right side
if (pos + tmp <= N)
{
pos += tmp;
}
else
{
pos -= tmp;
}
// Print the path
document.write(pos + " ");;
coin -= tmp;
jump -= 1;
}
}
}
// Driver Code
let N = 5, K = 4, M = 12;
// Function Call
print_path(N, K, M);
</script>
5 1 4 5
Complejidad temporal: O(K)
Espacio auxiliar: O(1)