Suma máxima posible de cuadrados de elementos de pila que satisfacen las propiedades dadas

Posted on by Rudeus Greyrat

Dados dos enteros S y N, la tarea es encontrar la máxima suma posible de cuadrados de N enteros que se pueden colocar en una pila de modo que se cumplan las siguientes propiedades:

  • El entero en la parte superior de la pila no debe ser más pequeño que el elemento inmediatamente debajo.
  • Todos los elementos de la pila deben estar en el rango [1, 9] .
  • La suma de los elementos de la pila debe ser exactamente igual a S .

Si es imposible obtener dicho arreglo, imprima -1 .

Ejemplos:

Entrada: S = 12, N = 3
Salida: 86
Explicación:
La disposición de pila [9, 2, 1] genera la suma 12 (= S), por lo tanto, satisface las propiedades.
Por tanto, máxima suma de cuadrados posible = 9 * 9 + 2 * 2 + 1 * 1= 81 + 4 + 1 = 86

Entrada: S = 11, N = 1
Salida: -1

Enfoque: siga los pasos a continuación para resolver el problema:

  1. Compruebe si S es válido, es decir, si se encuentra dentro del rango [N, 9 * N] .
  2. Inicialice una variable, digamos res para almacenar la suma máxima de cuadrados de los elementos de la pila.
  3. El valor mínimo de un entero en la pila puede ser 1, así que inicialice todos los elementos de la pila con 1. Por lo tanto, reste N de S.
  4. Ahora, verifique el número de enteros que tienen un valor de más de 1. Para esto, agregue 8 (si es posible) a los enteros comenzando desde la base de la pila y continúe sumando hasta S > 0 .
  5. Al final, agregue S % 8 al entero actual y complete todos los elementos restantes de la pila con 1.
  6. Finalmente, agregue la suma de los cuadrados de los elementos de la pila.

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// sum of squares of stack elements
void maxSumOfSquares(int N,
                     int S)
{
  // Stores the sum ofsquares
  // of stack elements
  int res = 0;
 
  // Check if sum is valid
  if (S < N || S > 9 * N)
  {
    cout << (-1);
    return;
  }
 
  // Initialize all stack
  // elements with 1
  S = S - N;
 
  // Stores the count the
  // number of stack elements
  // not equal to 1
  int c = 0;
 
  // Add the sum of squares
  // of stack elements not
  // equal to 1
  while (S > 0)
  {
    c++;
    if (S / 8 > 0)
    {
      res += 9 * 9;
      S -= 8;
    }
    else
    {
      res += (S + 1) *
             (S + 1);
      break;
    }
  }
 
  // Add 1 * 1 to res as the
  // remaining stack elements
  // are 1
  res = res + (N - c);
 
  // Print the result
  cout << (res);
}
 
// Driver Code
int main()
{
  int N = 3;
  int S = 12;
 
  // Function call
  maxSumOfSquares(N, S);
}
// This code is contributed by 29AjayKumar

Java

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the maximum
    // sum of squares of stack elements
    public static void maxSumOfSquares(
        int N, int S)
    {
        // Stores the sum ofsquares
        // of stack elements
        int res = 0;
 
        // Check if sum is valid
        if (S < N || S > 9 * N) {
 
            System.out.println(-1);
            return;
        }
 
        // Initialize all stack
        // elements with 1
        S = S - N;
 
        // Stores the count the
        // number of stack elements
        // not equal to 1
        int c = 0;
 
        // Add the sum of squares of
        // stack elements not equal to 1
        while (S > 0) {
            c++;
 
            if (S / 8 > 0) {
 
                res += 9 * 9;
                S -= 8;
            }
 
            else {
 
                res += (S + 1)
                       * (S + 1);
                break;
            }
        }
 
        // Add 1 * 1 to res as the
        // remaining stack elements are 1
        res = res + (N - c);
 
        // Print the result
        System.out.println(res);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int N = 3;
        int S = 12;
 
        // Function call
        maxSumOfSquares(N, S);
    }
}

Python3

# Python3 program to implement
# the above approach
 
# Function to find the maximum
# sum of squares of stack elements
def maxSumOfSquares(N, S):
     
    # Stores the sum ofsquares
    # of stack elements
    res = 0
 
    # Check if sum is valid
    if (S < N or S > 9 * N):
        cout << -1;
        return
 
    # Initialize all stack
    # elements with 1
    S = S - N
 
    # Stores the count the
    # number of stack elements
    # not equal to 1
    c = 0
 
    # Add the sum of squares of
    # stack elements not equal to 1
    while (S > 0):
        c += 1
 
        if (S // 8 > 0):
            res += 9 * 9
            S -= 8
        else:
            res += (S + 1) * (S + 1)
            break
 
    # Add 1 * 1 to res as the
    # remaining stack elements are 1
    res = res + (N - c)
 
    # Print the result
    print(res)
 
# Driver Code
if __name__ == '__main__':
     
    N = 3
    S = 12
 
    # Function call
    maxSumOfSquares(N, S)
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to find the maximum
// sum of squares of stack elements
public static void maxSumOfSquares(int N,
                                   int S)
{
  // Stores the sum ofsquares
  // of stack elements
  int res = 0;
 
  // Check if sum is valid
  if (S < N || S > 9 * N)
  {
    Console.WriteLine(-1);
    return;
  }
 
  // Initialize all stack
  // elements with 1
  S = S - N;
 
  // Stores the count the
  // number of stack elements
  // not equal to 1
  int c = 0;
 
  // Add the sum of squares of
  // stack elements not equal to 1
  while (S > 0)
  {
    c++;
 
    if (S / 8 > 0)
    {
      res += 9 * 9;
      S -= 8;
    }
 
    else
    {
      res += (S + 1) *
             (S + 1);
      break;
    }
  }
 
  // Add 1 * 1 to res
  // as the remaining
  // stack elements are 1
  res = res + (N - c);
 
  // Print the result
  Console.WriteLine(res);
}
 
// Driver Code
public static void Main(String []args)
{
  int N = 3;
  int S = 12;
 
  // Function call
  maxSumOfSquares(N, S);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// javascript program to implement
// the above approach   
// Function to find the maximum
    // sum of squares of stack elements
    function maxSumOfSquares(N , S) {
        // Stores the sum ofsquares
        // of stack elements
        var res = 0;
 
        // Check if sum is valid
        if (S < N || S > 9 * N) {
 
            document.write(-1);
            return;
        }
 
        // Initialize all stack
        // elements with 1
        S = S - N;
 
        // Stores the count the
        // number of stack elements
        // not equal to 1
        var c = 0;
 
        // Add the sum of squares of
        // stack elements not equal to 1
        while (S > 0) {
            c++;
 
            if (parseInt(S / 8) > 0) {
 
                res += 9 * 9;
                S -= 8;
            }
 
            else {
 
                res += (S + 1) * (S + 1);
                break;
            }
        }
 
        // Add 1 * 1 to res as the
        // remaining stack elements are 1
        res = res + (N - c);
 
        // Print the result
        document.write(res);
    }
 
    // Driver Code
     
        var N = 3;
        var S = 12;
 
        // Function call
        maxSumOfSquares(N, S);
 
// This code contributed by aashish1995
</script>
Producción: 

86

 

Complejidad temporal : O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por kunalsg18elec 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 *