Dados dos arreglos de enteros edades y paquetes donde edades almacena las edades de diferentes estudiantes y un elemento de paquete almacena la cantidad de dulces que tiene ese paquete (la array completa representa la cantidad de paquetes). Los dulces se pueden distribuir entre los estudiantes de tal manera que:
- Cada estudiante debe recibir solo un paquete de dulces.
- Todos los estudiantes de la misma edad deben recibir la misma cantidad de dulces.
- Un alumno mayor debe recibir más caramelos que todos los alumnos menores que él.
La tarea es determinar si es posible distribuir dulces de la manera descrita. Si es posible, escriba Sí, de lo contrario, escriba No.
Ejemplos:
Entrada: edades[] = {5, 15, 10}, packs[] = {2, 2, 2, 3, 3, 4}
Salida: SÍ
Hay 3 alumnos de 5, 15 y 10 años.Y hay 6 paquetes de caramelos que contienen 2, 2, 2, 3, 3, 4 caramelos respectivamente.
Le daremos un paquete que contiene 2 dulces al estudiante de 5 años, un paquete que contiene 3 dulces al estudiante de 10 años y el paquete que contiene 4 dulces al estudiante de 15 años.Entrada: edades[] = {5, 5, 6, 7}, paquetes[] = {5, 4, 6, 6}
Salida: NO
Acercarse:
- Haga 2 arrays de frecuencia, una que almacenará la cantidad de estudiantes con una edad particular y otra que almacenará la cantidad de paquetes con una cantidad particular de dulces.
- Luego recorra la array de frecuencias por edades comenzando desde la edad más joven y para cada edad en forma ascendente trate de encontrar los paquetes de dulces que son mayores o iguales al número de estudiantes para la edad seleccionada (comenzando desde la menor cantidad de dulces que tiene un paquete )
- Si el caso anterior falla, la respuesta es No; de lo contrario, repita los pasos anteriores hasta que todos los estudiantes hayan recibido los dulces y escriba Sí al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to check The validity of distribution
void check_distribution(int n, int k,
int age[], int candy[])
{
// Storing the max age of all
// students + 1
int mxage = *(std::max_element(
age, age + n)) + 1;
// Storing the max candy + 1
int mxcandy = *(std::max_element(
candy, candy + k)) + 1;
int fr1[mxage] = {0};
int fr2[mxcandy] = {0};
// Creating the frequency array of
// the age of students
for(int j = 0; j < n; j++)
{
fr1[age[j]] += 1;
}
// Creating the frequency array of the
// packets of candies
for(int j = 0; j < k; j++)
{
fr2[candy[j]] += 1;
}
// Pointer to tell whether we have reached
// the end of candy frequency array
k = 0;
// Flag to tell if distribution
// is possible or not
bool Tf = true;
for(int j = 0; j < mxage; j++)
{
if (fr1[j] == 0)
continue;
// Flag to tell if we can choose
// some candy packets for the
// students with age j
bool flag = false;
while (k < mxcandy)
{
// If the quantity of packets is
// greater than or equal to the
// number of students of age j,
// then we can choose these
// packets for the students
if (fr1[j] <= fr2[k])
{
flag = true;
break;
}
k += 1;
}
// Start searching from k + 1
// in next operation
k = k + 1;
// If we cannot choose any packets
// then the answer is NO
if (flag == false)
{
Tf = false;
break;
}
}
if (Tf)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
// Driver code
int main()
{
int age[] = { 5, 15, 10 };
int candy[] = { 2, 2, 2, 3, 3, 4 };
int n = sizeof(age) / sizeof(age[0]);
int k = sizeof(candy) / sizeof(candy[0]);
check_distribution(n, k, age, candy);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java implementation of the approach
import java.util.*;
class Main
{
// Function to check The validity of distribution
public static void check_distribution(int n, int k,
int age[], int candy[])
{
// Storing the max age of all
// students + 1
int mxage = age[0];
for(int i = 0; i < age.length; i++)
{
if(mxage < age[i])
{
mxage = age[i];
}
}
// Storing the max candy + 1
int mxcandy = candy[0];
for(int i = 0; i < candy.length; i++)
{
if(mxcandy < candy[i])
{
mxcandy = candy[i];
}
}
int fr1[] = new int[mxage + 1];
Arrays.fill(fr1, 0);
int fr2[] = new int[mxcandy + 1];
Arrays.fill(fr2, 0);
// Creating the frequency array of
// the age of students
for(int j = 0; j < n; j++)
{
fr1[age[j]] += 1;
}
// Creating the frequency array of the
// packets of candies
for(int j = 0; j < k; j++)
{
fr2[candy[j]] += 1;
}
// Pointer to tell whether we have reached
// the end of candy frequency array
k = 0;
// Flag to tell if distribution
// is possible or not
boolean Tf = true;
for(int j = 0; j < mxage; j++)
{
if (fr1[j] == 0)
continue;
// Flag to tell if we can choose
// some candy packets for the
// students with age j
boolean flag = false;
while (k < mxcandy)
{
// If the quantity of packets is
// greater than or equal to the
// number of students of age j,
// then we can choose these
// packets for the students
if (fr1[j] <= fr2[k])
{
flag = true;
break;
}
k += 1;
}
// Start searching from k + 1
// in next operation
k = k + 1;
// If we cannot choose any packets
// then the answer is NO
if (flag == false)
{
Tf = false;
break;
}
}
if (Tf)
System.out.println("YES");
else
System.out.println("NO");
}
// Driver code
public static void main(String[] args)
{
int age[] = { 5, 15, 10 };
int candy[] = { 2, 2, 2, 3, 3, 4 };
int n = age.length;
int k = candy.length;
check_distribution(n, k, age, candy);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 implementation of the approach
# Function to check The validity of distribution
def check_distribution(n, k, age, candy):
# Storing the max age of all students + 1
mxage = max(age)+1
# Storing the max candy + 1
mxcandy = max(candy)+1
fr1 = [0] * mxage
fr2 = [0] * mxcandy
# creating the frequency array of the
# age of students
for j in range(n):
fr1[age[j]] += 1
# Creating the frequency array of the
# packets of candies
for j in range(k):
fr2[candy[j]] += 1
# pointer to tell whether we have reached
# the end of candy frequency array
k = 0
# Flag to tell if distribution is possible or not
Tf = True
for j in range(mxage):
if (fr1[j] == 0):
continue
# Flag to tell if we can choose some
# candy packets for the students with age j
flag = False
while (k < mxcandy):
# If the quantity of packets is greater
# than or equal to the number of students
# of age j, then we can choose these
# packets for the students
if (fr1[j] <= fr2[k]):
flag = True
break
k += 1
# Start searching from k + 1 in next operation
k = k + 1
# If we cannot choose any packets
# then the answer is NO
if (flag == False):
Tf = False
break
if (Tf):
print("YES")
else:
print("NO")
# Driver code
age = [5, 15, 10]
candy = [2, 2, 2, 3, 3, 4]
n = len(age)
k = len(candy)
check_distribution(n, k, age, candy)
C#
// C# implementation of the approach
using System.IO;
using System;
class GFG
{
// Function to check The validity of distribution
static void check_distribution(int n,int k,
int[] age,int[] candy)
{
// Storing the max age of all
// students + 1
int mxage = age[0];
for(int i = 0; i < age.Length; i++)
{
if(mxage < age[i])
{
mxage = age[i];
}
}
// Storing the max candy + 1
int mxcandy = candy[0];
for(int i = 0; i < candy.Length; i++)
{
if(mxcandy < candy[i])
{
mxcandy = candy[i];
}
}
int[] fr1 = new int[mxage + 1];
Array.Fill(fr1, 0);
int[] fr2 = new int[mxcandy + 1];
Array.Fill(fr2, 0);
// Creating the frequency array of
// the age of students
for(int j = 0; j < n; j++)
{
fr1[age[j]] += 1;
}
// Creating the frequency array of the
// packets of candies
for(int j = 0; j < k; j++)
{
fr2[candy[j]] += 1;
}
// Pointer to tell whether we have reached
// the end of candy frequency array
k = 0;
// Flag to tell if distribution
// is possible or not
bool Tf = true;
for(int j = 0; j < mxage; j++)
{
if(fr1[j] == 0)
{
continue;
}
// Flag to tell if we can choose
// some candy packets for the
// students with age j
bool flag = false;
while (k < mxcandy)
{
// If the quantity of packets is
// greater than or equal to the
// number of students of age j,
// then we can choose these
// packets for the students
if (fr1[j] <= fr2[k])
{
flag = true;
break;
}
k += 1;
}
// Start searching from k + 1
// in next operation
k = k + 1;
// If we cannot choose any packets
// then the answer is NO
if (flag == false)
{
Tf = false;
break;
}
}
if(Tf)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
// Driver code
static void Main()
{
int[] age = {5, 15, 10};
int[] candy = { 2, 2, 2, 3, 3, 4 };
int n = age.Length;
int k = candy.Length;
check_distribution(n, k, age, candy);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript implementation of the approach
// Function to check The validity of distribution
function check_distribution(n, k, age, candy)
{
// Storing the max age of all
// students + 1
let mxage = age[0];
for(let i = 0; i < age.length; i++)
{
if(mxage < age[i])
{
mxage = age[i];
}
}
// Storing the max candy + 1
let mxcandy = candy[0];
for(let i = 0; i < candy.length; i++)
{
if(mxcandy < candy[i])
{
mxcandy = candy[i];
}
}
let fr1 = new Array(mxage + 1);
fr1.fill(0);
let fr2 = new Array(mxcandy + 1);
fr2.fill(0);
// Creating the frequency array of
// the age of students
for(let j = 0; j < n; j++)
{
fr1[age[j]] += 1;
}
// Creating the frequency array of the
// packets of candies
for(let j = 0; j < k; j++)
{
fr2[candy[j]] += 1;
}
// Pointer to tell whether we have reached
// the end of candy frequency array
k = 0;
// Flag to tell if distribution
// is possible or not
let Tf = true;
for(let j = 0; j < mxage; j++)
{
if(fr1[j] == 0)
{
continue;
}
// Flag to tell if we can choose
// some candy packets for the
// students with age j
let flag = false;
while (k < mxcandy)
{
// If the quantity of packets is
// greater than or equal to the
// number of students of age j,
// then we can choose these
// packets for the students
if (fr1[j] <= fr2[k])
{
flag = true;
break;
}
k += 1;
}
// Start searching from k + 1
// in next operation
k = k + 1;
// If we cannot choose any packets
// then the answer is NO
if (flag == false)
{
Tf = false;
break;
}
}
if(Tf)
{
document.write("YES");
}
else
{
document.write("NO");
}
}
let age = [5, 15, 10];
let candy = [ 2, 2, 2, 3, 3, 4 ];
let n = age.length;
let k = candy.length;
check_distribution(n, k, age, candy);
// This code is contributed by suresh07.
</script>
Producción:
YES