Número mínimo de manzanas a recolectar de los árboles para garantizar M manzanas rojas

Hay diferentes tipos de manzanos en las cuatro direcciones (Este, Oeste, Norte, Sur), que pueden producir tanto manzanas rojas como verdes, de modo que cada árbol produce exactamente manzanas K, de la siguiente manera:

• N : número de árboles al norte que no tienen manzanas rojas.
• S : número de árboles al sur que no tienen manzanas verdes.
• W : número de árboles en el oeste que tienen algunas manzanas rojas.
• E – número de árboles en el este tienen algunas manzanas verdes.

Sin embargo, los colores de las manzanas no se pueden distinguir fuera de la casa. Entonces, la tarea es encontrar el número mínimo de manzanas que se recolectarán de los árboles para garantizar M manzanas rojas. Si no es posible, imprima -1.

Ejemplos:

Entrada: M = 10, K = 15, N = 0, S = 1, W = 0, E = 0
Salida: 10
Explicación: simplemente obtiene 10 manzanas del primer árbol del sur

Entrada: M = 10, K = 15, N = 3, S = 0, W = 1, E = 0
Salida: -1
Explicación: No hay manzanas rojas en el Sur, Norte y Este. Pero en Occidente hay al menos 1 manzana roja y el total de árboles es 1, por lo tanto, el total no. de manzana roja garantizada es 1 * 1 = 1 que es menor que M.

Enfoque:   Cada manzana en el sur asegura que es roja. Primero, toma una manzana del sur. En Oriente y Occidente, hay al menos 1 manzana roja en cada árbol. Por eso, para garantizar se considera que solo hay 1 manzana roja en cada árbol en el este y el oeste. Para el norte no hay manzana roja, así que descuida eso. Siga los pasos a continuación para resolver el problema:

• Si M es menor que igual a S*K , imprima M.
• De lo contrario, si M es menor que igual a S*K+E+W , imprima S*K + (MS*K) * K
• De lo contrario , imprima -1.

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

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to minimum no. of apples
int minApples(int M,int K,int N,int S,int W,int E){
    // If we get all required apple
    // from South
    if(M <= S * K)
        return M;
 
    // If we required trees at
    // East and West
    else if(M <= S * K + E + W)
        return S * K + (M-S * K) * K;
 
    // If we doesn't have enough
    // red apples
    else
        return -1;
 
}
 
// Driver Code
int main(){
     
    // No. of red apple for gift
    int M = 10;
 
    // No. of red apple in each tree
    int K = 15;
 
    // No. of tree in North
    int N = 0;
 
    // No. of tree in South
    int S = 1;
 
    // No. of tree in West
    int W = 0;
 
    // No. of tree in East
    int E = 0;
 
    // Function Call
    int ans = minApples(M,K,N,S,W,E);
    cout<<ans<<endl;
 
}
 
// This code is contributed by ipg2016107.

// Java program for the above approach
import java.io.*;
class GFG {
 
// Function to minimum no. of apples
static int minApples(int M,int K,int N,int S,int W,int E)
{
   
    // If we get all required apple
    // from South
    if(M <= S * K)
        return M;
 
    // If we required trees at
    // East and West
    else if(M <= S * K + E + W)
        return S * K + (M-S * K) * K;
 
    // If we doesn't have enough
    // red apples
    else
        return -1;
}
 
// Driver code
public static void main(String[] args)
{
    // No. of red apple for gift
    int M = 10;
 
    // No. of red apple in each tree
    int K = 15;
 
    // No. of tree in North
    int N = 0;
 
    // No. of tree in South
    int S = 1;
 
    // No. of tree in West
    int W = 0;
 
    // No. of tree in East
    int E = 0;
 
    // Function Call
    int ans = minApples(M,K,N,S,W,E);
    System.out.println(ans);
}
}
 
// This code is contributed by code_hunt.

# Python program for the above approach
 
 
# Function to minimum no. of apples
def minApples():
 
    # If we get all required apple
    # from South
    if M <= S * K:
        return M
 
    # If we required trees at
    # East and West
    elif M <= S * K + E + W:
        return S * K + (M-S * K) * K
 
    # If we doesn't have enough
    # red apples
    else:
        return -1
 
 
# Driver Code
if __name__ == "__main__":
 
    # No. of red apple for gift
    M = 10
 
    # No. of red apple in each tree
    K = 15
 
    # No. of tree in North
    N = 0
 
    # No. of tree in South
    S = 1
 
    # No. of tree in West
    W = 0
 
    # No. of tree in East
    E = 0
 
    # Function Call
    ans = minApples()
    print(ans)

// C# program for the above approach
using System;
 
class GFG{
 
// Function to minimum no. of apples
static int minApples(int M, int K, int N,
                     int S, int W, int E)
{
     
    // If we get all required apple
    // from South
    if (M <= S * K)
        return M;
 
    // If we required trees at
    // East and West
    else if (M <= S * K + E + W)
        return S * K + (M - S * K) * K;
 
    // If we doesn't have enough
    // red apples
    else
        return -1;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // No. of red apple for gift
    int M = 10;
 
    // No. of red apple in each tree
    int K = 15;
 
    // No. of tree in North
    int N = 0;
 
    // No. of tree in South
    int S = 1;
 
    // No. of tree in West
    int W = 0;
 
    // No. of tree in East
    int E = 0;
 
    // Function Call
    int ans = minApples(M, K, N, S, W, E);
    Console.Write(ans);
}
}
 
// This code is contributed by shivanisinghss2110

<script>
 
      // JavaScript program for the above approach;
 
      // Function to minimum no. of apples
      function minApples() {
 
          // If we get all required apple
          // from South
          if (M <= S * K)
              return M;
 
          // If we required trees at
          // East and West
          else if (M <= S * K + E + W)
              return S * K + (M - S * K) * K;
 
          // If we doesn't have enough
          // red apples
          else
              return -1;
      }
 
      // Driver Code
 
      // No. of red apple for gift
      M = 10
 
      // No. of red apple in each tree
      K = 15
 
      // No. of tree in North
      N = 0
 
      // No. of tree in South
      S = 1
 
      // No. of tree in West
      W = 0
 
      // No. of tree in East
      E = 0
 
      // Function Call
      ans = minApples()
      document.write(ans);
 
 // This code is contributed by Potta Lokesh
  </script>

10

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)