Costo mínimo para llegar a un punto N desde 0 con dos operaciones diferentes permitidas

Dados los números enteros N, P y Q, donde N indica la posición de destino. La tarea es pasar de la posición 0 a la posición N con el mínimo costo posible e imprimir el costo calculado. Todos los movimientos válidos son: 
 

1. Desde la posición X puedes ir a la posición X + 1 con un costo de P
2. O bien, puede ir a la posición 2 * X con un costo de Q

Ejemplos: 
 

Entrada: N = 1, P = 3, Q = 4 
Salida: 3 
Pasar de la posición 0 a la 1ra posición con costo = 3.
Entrada: N = 9, P = 5, Q = 1 
Salida: 13 
Pasar de la posición 0 a la 1ra posición con costo = 5, 
luego 1 a 2 con costo = 1, 
luego 2 a 4 con costo = 1, 
luego 4 a 8 con costo = 1, 
finalmente 8 a 9 con costo = 5. 
Costo total = 5 + 1 + 1 + 1 + 5 = 13. 
 

Enfoque: en lugar de ir desde el principio hasta el destino, podemos comenzar a movernos desde el destino a la posición inicial y realizar un seguimiento del costo de los saltos. 
 

• Si N es impar, entonces el único movimiento válido que podría llevarnos aquí es N-1 a N con un costo de P.
• Si N es par, entonces calculamos el costo de pasar de N a N/2 posición con ambos movimientos y tomamos el mínimo de ellos.
• Cuando N es igual a 0 , devolvemos nuestro costo total calculado.

A continuación se muestra la implementación del enfoque anterior:
 

// CPP implementation of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return minimum
// cost to reach destination
int minCost(int N, int P, int Q)
{
    // Initialize cost to 0
    int cost = 0;
 
    // going backwards until we
    // reach initial position
    while (N > 0) {
 
        if (N & 1) {
            cost += P;
            N--;
        }
        else {
            int temp = N / 2;
 
            // if 2*X jump is
            // better than X+1
            if (temp * P > Q)
                cost += Q;
            // if X+1 jump is better
            else
                cost += P * temp;
 
            N /= 2;
        }
    }
 
    // return cost
    return cost;
}
 
// Driver program
int main()
{
    int N = 9, P = 5, Q = 1;
 
    cout << minCost(N, P, Q);
 
    return 0;
}

// Java implementation of above approach
 
class GFG{
// Function to return minimum
// cost to reach destination
static int minCost(int N, int P, int Q)
{
    // Initialize cost to 0
    int cost = 0;
 
    // going backwards until we
    // reach initial position
    while (N > 0) {
 
        if ((N & 1)>0) {
            cost += P;
            N--;
        }
        else {
            int temp = N / 2;
 
            // if 2*X jump is
            // better than X+1
            if (temp * P > Q)
                cost += Q;
            // if X+1 jump is better
            else
                cost += P * temp;
 
            N /= 2;
        }
    }
 
    // return cost
    return cost;
}
 
// Driver program
public static void main(String[] args)
{
    int N = 9, P = 5, Q = 1;
 
    System.out.println(minCost(N, P, Q));
}
}
// This code is contributed by mits

# Python implementation of above approach
 
 
# Function to return minimum
# cost to reach destination
 
def minCost(N,P,Q):
    # Initialize cost to 0
    cost = 0
   
    # going backwards until we
    # reach initial position
    while (N > 0): 
        if (N & 1):
            cost += P
            N-=1
        else:
            temp = N // 2;
   
            # if 2*X jump is
            # better than X+1
            if (temp * P > Q):
                cost += Q
            # if X+1 jump is better
            else:
                cost += P * temp
            N //= 2
    return cost
 
   
# Driver program
N = 9
P = 5
Q = 1
print(minCost(N, P, Q))
#this code is improved by sahilshelangia

// C# implementation of above approach
 
class GFG
{
// Function to return minimum
// cost to reach destination
static int minCost(int N, int P, int Q)
{
    // Initialize cost to 0
    int cost = 0;
 
    // going backwards until we
    // reach initial position
    while (N > 0)
    {
 
        if ((N & 1) > 0)
        {
            cost += P;
            N--;
        }
        else
        {
            int temp = N / 2;
 
            // if 2*X jump is
            // better than X+1
            if (temp * P > Q)
                cost += Q;
                 
            // if X+1 jump is better
            else
                cost += P * temp;
 
            N /= 2;
        }
    }
 
    // return cost
    return cost;
}
 
// Driver Code
static void Main()
{
    int N = 9, P = 5, Q = 1;
 
    System.Console.WriteLine(minCost(N, P, Q));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation of above approach
 
// Function to return minimum
// cost to reach destination
function minCost($N, $P, $Q)
{
    // Initialize cost to 0
    $cost = 0;
 
    // going backwards until we
    // reach initial position
    while ($N > 0)
    {
 
        if ($N & 1)
        {
            $cost += $P;
            $N--;
        }
        else
        {
            $temp = $N / 2;
 
            // if 2*X jump is
            // better than X+1
            if ($temp * $P > $Q)
                $cost += $Q;
                 
            // if X+1 jump is better
            else
                $cost += $P * $temp;
 
            $N /= 2;
        }
    }
 
    // return cost
    return $cost;
}
 
// Driver Code
$N = 9; $P = 5; $Q = 1;
 
echo minCost($N, $P, $Q);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
//Javascript implementation of above approach
 
// Function to return minimum
// cost to reach destination
function minCost( N, P, Q)
{
    // Initialize cost to 0
    var cost = 0;
 
    // going backwards until we
    // reach initial position
    while (N > 0) {
 
        if (N & 1) {
            cost += P;
            N--;
        }
        else {
            var temp =parseInt( N / 2);
 
            // if 2*X jump is
            // better than X+1
            if (temp * P > Q)
                cost += Q;
            // if X+1 jump is better
            else
                cost += P * temp;
 
            N = parseInt(N / 2);
        }
    }
 
    // return cost
    return cost;
}
var N = 9, P = 5, Q = 1;
 
document.write( minCost(N, P, Q));
 
//This code is contributed by SoumikMondal
</script>

13

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)