Dados dos números enteros A y B , que representan el conteo de objetos de dos tipos diferentes, y otro número entero N que representa el número de estantes, la tarea es colocar todos los objetos en los N estantes dados respetando las siguientes reglas:
- Cualquier estantería no puede contener objetos de tipo A y tipo B al mismo tiempo.
- Ningún estante puede contener más de K objetos de Tipo-A o L objetos de tipo B.
Si es posible colocar todos los artículos en N estantes, escriba «SÍ» . De lo contrario, escriba “NO” .
Ejemplos:
Entrada: A = 3, B = 3, N = 3, K = 4, M = 2
Salida: SÍ
Explicación:
se pueden colocar 3 artículos tipo A en 1 estante, ya que el límite máximo es 4.
Se pueden colocar 3 artículos tipo B colocarse en 2 estantes, ya que el límite máximo es 2.
Dado que el número requerido de estantes no excede N, la asignación es posible.
Entrada: A = 6, B = 7, N = 3, K = 4, L = 5
Salida: NO
Explicación:
6 artículos tipo A requieren 2 estantes, ya que el límite máximo es 4.
7 artículos tipo B requieren 2 estantes, como límite máximo es 5.
Dado que el número requerido de estantes excede N, la asignación no es posible.
Planteamiento:
Para resolver el problema, necesitamos contar el número mínimo de estantes requeridos para colocar todos los objetos y verificar si excede N o no. Siga los pasos a continuación:
- Cuente la cantidad mínima de elementos necesarios para colocar elementos de tipo A , digamos needa . Dado que los artículos K Tipo-A se pueden colocar como máximo en un solo estante, surgen las siguientes dos condiciones:
- Si A es divisible por K , todos los artículos de tipo A se pueden colocar en los estantes A/K .
- De lo contrario, los artículos A % K deben colocarse en 1 estante y el resto en estantes A / K. Por lo tanto, se requieren A / K + 1 estantes para este caso.
- De manera similar, calcule la cantidad mínima de estantes necesarios para colocar artículos de tipo B, por ejemplo, needb .
- Si needa + needb excede N , la asignación no es posible. De lo contrario, es posible.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return if allocation
// is possible or not
bool isPossible(int A, int B, int N,
int K, int L)
{
// Stores the shelves needed
// for items of type-A and type-B
int needa, needb;
// Find number of shelves
// needed for items of type-A
if (A % K == 0)
// Fill A / K shelves fully
// by the items of type-A
needa = A / K;
// Otherwise
else
// Fill A / L shelves fully
// and add remaining to an
// extra shelf
needa = A / K + 1;
// Find number of shelves
// needed for items of type-B
if (B % L == 0)
// Fill B / L shelves fully
// by the items of type-B
needb = B / L;
else
// Fill B / L shelves fully
// and add remaining to an
// an extra shelf
needb = B / L + 1;
// Total shelves needed
int total = needa + needb;
// If required shelves exceed N
if (total > N)
return false;
else
return true;
}
// Driver Program
int main()
{
int A = 3, B = 3, N = 3;
int K = 4, M = 2;
if (isPossible(A, B, N, K, M))
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
Java
// Java implementation of the above approach
class GFG{
// Function to return if allocation
// is possible or not
static boolean isPossible(int A, int B,
int N, int K,
int L)
{
// Stores the shelves needed
// for items of type-A and type-B
int needa, needb;
// Find number of shelves
// needed for items of type-A
if (A % K == 0)
// Fill A / K shelves fully
// by the items of type-A
needa = A / K;
// Otherwise
else
// Fill A / L shelves fully
// and add remaining to an
// extra shelf
needa = A / K + 1;
// Find number of shelves
// needed for items of type-B
if (B % L == 0)
// Fill B / L shelves fully
// by the items of type-B
needb = B / L;
else
// Fill B / L shelves fully
// and add remaining to an
// an extra shelf
needb = B / L + 1;
// Total shelves needed
int total = needa + needb;
// If required shelves exceed N
if (total > N)
return false;
else
return true;
}
// Driver code
public static void main(String[] args)
{
int A = 3, B = 3, N = 3;
int K = 4, M = 2;
if (isPossible(A, B, N, K, M))
System.out.print("YES" + "\n");
else
System.out.print("NO" + "\n");
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 implementation of the
# above approach
# Function to return if allocation
# is possible or not
def isPossible(A, B, N, K, L):
# Stores the shelves needed
# for items of type-A and type-B
needa = 0
needb = 0
# Find number of shelves
# needed for items of type-A
if (A % K == 0):
# Fill A / K shelves fully
# by the items of type-A
needa = A // K;
# Otherwise
else:
# Fill A / L shelves fully
# and add remaining to an
# extra shelf
needa = A // K + 1
# Find number of shelves
# needed for items of type-B
if (B % L == 0):
# Fill B / L shelves fully
# by the items of type-B
needb = B // L
else:
# Fill B / L shelves fully
# and add remaining to an
# an extra shelf
needb = B // L + 1
# Total shelves needed
total = needa + needb
# If required shelves exceed N
if (total > N):
return False
else:
return True
# Driver Code
if __name__=='__main__':
A, B, N = 3, 3, 3
K, M = 4, 2
if (isPossible(A, B, N, K, M)):
print('YES')
else:
print('NO')
# This code is contributed by rutvik_56
C#
// C# implementation of the above approach
using System;
class GFG{
// Function to return if allocation
// is possible or not
static bool isPossible(int A, int B,
int N, int K,
int L)
{
// Stores the shelves needed
// for items of type-A and type-B
int needa, needb;
// Find number of shelves
// needed for items of type-A
if (A % K == 0)
// Fill A / K shelves fully
// by the items of type-A
needa = A / K;
// Otherwise
else
// Fill A / L shelves fully
// and add remaining to an
// extra shelf
needa = A / K + 1;
// Find number of shelves
// needed for items of type-B
if (B % L == 0)
// Fill B / L shelves fully
// by the items of type-B
needb = B / L;
else
// Fill B / L shelves fully
// and add remaining to an
// an extra shelf
needb = B / L + 1;
// Total shelves needed
int total = needa + needb;
// If required shelves exceed N
if (total > N)
return false;
else
return true;
}
// Driver code
public static void Main(String[] args)
{
int A = 3, B = 3, N = 3;
int K = 4, M = 2;
if (isPossible(A, B, N, K, M))
Console.Write("YES" + "\n");
else
Console.Write("NO" + "\n");
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to return if allocation
// is possible or not
function isPossible(A, B, N, K, L)
{
// Stores the shelves needed
// for items of type-A and type-B
let needa, needb;
// Find number of shelves
// needed for items of type-A
if (A % K == 0)
// Fill A / K shelves fully
// by the items of type-A
needa = Math.floor(A / K);
// Otherwise
else
// Fill A / L shelves fully
// and add remaining to an
// extra shelf
needa = Math.floor(A / K) + 1;
// Find number of shelves
// needed for items of type-B
if (B % L == 0)
// Fill B / L shelves fully
// by the items of type-B
needb = Math.floor(B / L);
else
// Fill B / L shelves fully
// and add remaining to an
// an extra shelf
needb = Math.floor(B / L) + 1;
// Total shelves needed
let total = needa + needb;
// If required shelves exceed N
if (total > N)
return false;
else
return true;
}
// Driver code
let A = 3, B = 3, N = 3;
let K = 4, M = 2;
if (isPossible(A, B, N, K, M))
document.write("YES" + "<br/>");
else
document.write("NO" + "<br/>");
// This code is contributed by sanjoy_62.
</script>
Producción:
YES
Complejidad temporal: O(1)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rajasek155 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA