Dados N dulces, M personas y una array arr[] de M enteros positivos, la tarea es encontrar el valor mínimo de K tal que una Persona A pueda consumir el total de al menos un límite de (N/(M + 1)) dulces de acuerdo con las siguientes reglas:
- En el primer turno, la Persona A consume un mínimo de la cantidad de dulces que quedan y K .
- En los siguientes M turnos, cada i -ésima Persona sobre el rango [0, M-1] consume el piso del arr[i] porcentaje de los dulces restantes.
- Repita los pasos anteriores, hasta que no queden dulces.
Ejemplos:
Entrada: N = 13, M = 1, arr[] = {50}
Salida: 3
Explicación:
Para el valor K como 3, la buena parte es el techo de (13/2) = 7. Los siguientes son los turnos que toma lugar:
- La persona A toma min(3,13)=3 caramelos. Por lo tanto, los dulces que quedan = 13 – 3 = 10.
- La persona 0 toma arr[0](= 50)% de los 10 dulces restantes, es decir, 5 dulces. Por lo tanto, los dulces que quedan = 10 – 5 = 5.
- La persona A toma min(3,5)=3 caramelos. Por lo tanto, los dulces que quedan = 5 – 3 = 2.
- La persona 0 toma arr[0](= 50)% de los 2 dulces restantes, es decir, 1 dulce. Por lo tanto, los dulces que quedan = 2 – 1 = 1.
- La persona A toma 1 caramelo. Por lo tanto, los dulces que quedan = 1 – 1 = 0.
Después de los turnos anteriores, los dulces tomados por la persona son 3 + 3 + 1 = 7, que es al menos (N/(M + 1)) dulces, es decir, 13/2 = 6.
Entrada: N = 13, M = 2, arr[] = {40, 50}
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es verificar cada cantidad de dulces que la Persona A obtendrá para todos los valores posibles de K . Siga los pasos a continuación para resolver este problema:
- Encuentre el valor de (N/(M + 1)) y guárdelo en una variable, digamos bueno , ya que esta es la cantidad mínima de dulces que la Persona A quiere tomar.
- Iterar sobre todos los valores de K en el rango [1, N] y realizar los siguientes pasos:
- Para cada valor de K , simule el proceso mencionado anteriormente y cuente el número total de dulces que recibirá la Persona A.
- Si la cantidad de dulces es al menos el valor del bien , entonces sal del círculo . De lo contrario, continúa con la iteración .
- Después de completar los pasos anteriores, imprima el valor actual de K como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum value of
// K such that the first person gets
// at least (N/(M+1)) candies
void minimumK(vector<int> &arr, int M,
int N)
{
// Find the minimum required value
// of candies for the first person
int good = ceil((N * 1.0)
/ ((M + 1) * 1.0));
// Iterate K from [1, n]
for (int i = 1; i <= N; i++) {
int K = i;
// Total number of candies
int candies = N;
// Candies taken by Person 1
int taken = 0;
while (candies > 0) {
// Candies taken by 1st
// person is minimum of K
// and candies left
taken += min(K, candies);
candies -= min(K, candies);
// Traverse the array arr[]
for (int j = 0; j < M; j++) {
// Amount consumed by the
// person j
int consume = (arr[j]
* candies) / 100;
// Update the number
// of candies
candies -= consume;
}
}
// Good share of candies achieved
if (taken >= good) {
cout << i;
return;
}
}
}
// Driver Code
int main()
{
int N = 13, M = 1;
vector<int> arr = { 50 };
minimumK(arr, M, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find minimum value of
// K such that the first person gets
// at least (N/(M+1)) candies
static void minimumK(ArrayList<Integer> arr, int M,
int N)
{
// Find the minimum required value
// of candies for the first person
int good = (int)((N * 1.0) / ((M + 1) * 1.0)) + 1;
// Iterate K from [1, n]
for(int i = 1; i <= N; i++)
{
int K = i;
// Total number of candies
int candies = N;
// Candies taken by Person 1
int taken = 0;
while (candies > 0)
{
// Candies taken by 1st
// person is minimum of K
// and candies left
taken += Math.min(K, candies);
candies -= Math.min(K, candies);
// Traverse the array arr[]
for(int j = 0; j < M; j++)
{
// Amount consumed by the
// person j
int consume = (arr.get(j) * candies) / 100;
// Update the number
// of candies
candies -= consume;
}
}
// Good share of candies achieved
if (taken >= good)
{
System.out.print(i);
return;
}
}
}
// Driver Code
public static void main(String[] args)
{
int N = 13, M = 1;
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(50);
minimumK(arr, M, N);
}
}
// This code is contributed by subhammahato348
Python3
# Python 3 program for the above approach import math # Function to find minimum value of # K such that the first person gets # at least (N/(M+1)) candies def minimumK(arr, M, N): # Find the minimum required value # of candies for the first person good = math.ceil((N * 1.0) / ((M + 1) * 1.0)) # Iterate K from [1, n] for i in range(1, N + 1): K = i # Total number of candies candies = N # Candies taken by Person 1 taken = 0 while (candies > 0): # Candies taken by 1st # person is minimum of K # and candies left taken += min(K, candies) candies -= min(K, candies) # Traverse the array arr[] for j in range(M): # Amount consumed by the # person j consume = (arr[j] * candies) / 100 # Update the number # of candies candies -= consume # Good share of candies achieved if (taken >= good): print(i) return # Driver Code if __name__ == "__main__": N = 13 M = 1 arr = [50] minimumK(arr, M, N) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find minimum value of
// K such that the first person gets
// at least (N/(M+1)) candies
static void minimumK(List<int> arr, int M,
int N)
{
// Find the minimum required value
// of candies for the first person
int good = (int)((N * 1.0) / ((M + 1) * 1.0))+1;
// Iterate K from [1, n]
for (int i = 1; i <= N; i++) {
int K = i;
// Total number of candies
int candies = N;
// Candies taken by Person 1
int taken = 0;
while (candies > 0) {
// Candies taken by 1st
// person is minimum of K
// and candies left
taken += Math.Min(K, candies);
candies -= Math.Min(K, candies);
// Traverse the array arr[]
for (int j = 0; j < M; j++) {
// Amount consumed by the
// person j
int consume = (arr[j]
* candies) / 100;
// Update the number
// of candies
candies -= consume;
}
}
// Good share of candies achieved
if (taken >= good) {
Console.Write(i);
return;
}
}
}
// Driver Code
public static void Main()
{
int N = 13, M = 1;
List<int> arr = new List<int>();
arr.Add(50);
minimumK(arr, M, N);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to find minimum value of
// K such that the first person gets
// at least (N/(M+1)) candies
function minimumK(arr, M, N)
{
// Find the minimum required value
// of candies for the first person
let good = Math.floor((N * 1.0) / ((M + 1) * 1.0))+1;
// Iterate K from [1, n]
for (let i = 1; i <= N; i++) {
let K = i;
// Total number of candies
let candies = N;
// Candies taken by Person 1
let taken = 0;
while (candies > 0) {
// Candies taken by 1st
// person is minimum of K
// and candies left
taken += Math.min(K, candies);
candies -= Math.min(K, candies);
// Traverse the array arr[]
for (let j = 0; j < M; j++) {
// Amount consumed by the
// person j
let consume = (arr[j]
* candies) / 100;
// Update the number
// of candies
candies -= consume;
}
}
// Good share of candies achieved
if (taken >= good) {
document.write(i);
return;
}
}
}
// Driver Code
let N = 13, M = 1;
let arr = new Array();
arr.push(50);
minimumK(arr, M, N);
// This code is contributed by _Saurabh_Jaiswal
</script>
Producción:
3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Encuentre el valor de (N/(M + 1)) y guárdelo en una variable, digamos bueno , ya que esta es la cantidad mínima de dulces que la Persona A quiere tomar.
- Inicialice dos variables, digamos bajo y alto como 1 y N respectivamente.
- Iterar hasta que bajo sea menor que alto y realizar los siguientes pasos:
- Encuentre el valor de mid como (low + high)/2 .
- Encuentre el número mínimo de dulces tomados por la Persona A para el valor de K como medio simulando el proceso mencionado anteriormente.
- Si la cantidad de dulces tomados por la Persona A es al menos buena , actualice el valor de alto a medio . De lo contrario, actualice el valor de low como (mid + 1) .
- Después de completar los pasos anteriores, imprima el valor de alto como el valor mínimo resultante de K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the value of
// mid gives at least (N/(M + 1))
// candies or not
bool check(int K, int n, int m,
vector<int> arr,
int good_share)
{
int candies = n, taken = 0;
while (candies > 0) {
// Candies taken by 1st
// person is minimum of K
// and candies left
taken += min(K, candies);
candies -= min(K, candies);
// Traverse the given array
for (int j = 0; j < m; j++) {
// Amount consumed by
// person j
int consume = (arr[j] * candies) / 100;
// Update the count of
// candies
candies -= consume;
}
}
// Check if person 1 gets the
// good share of candies
return (taken >= good_share);
}
// Function to find minimum value of
// K such that the first person gets
// at least (N/(M+1)) candies
void minimumK(vector<int> &arr, int N,
int M)
{
// Find the minimum required value
// of candies for the first person
int good_share = ceil((N * 1.0)
/ ((M + 1) * 1.0));
int lo = 1, hi = N;
// Iterate until low is less
// than or equal to mid
while (lo < hi) {
// Find the value of mid
int mid = (lo + hi) / 2;
// Check for mid, whether it
// can be the possible value
// of K or not
if (check(mid, N, M, arr,
good_share)) {
// Update the value of hi
hi = mid;
}
// Otherwise, update the
// value of lo
else {
lo = mid + 1;
}
}
// Print the resultant minimum
// value of K
cout << hi;
}
// Driver Code
int main()
{
int N = 13, M = 1;
vector<int> arr = { 50 };
minimumK(arr, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to check if the value of
// mid gives at least (N/(M + 1))
// candies or not
static boolean check(int K, int n, int m,
ArrayList<Integer> arr,
int good_share)
{
int candies = n, taken = 0;
while (candies > 0) {
// Candies taken by 1st
// person is minimum of K
// and candies left
taken += Math.min(K, candies);
candies -= Math.min(K, candies);
// Traverse the given array
for (int j = 0; j < m; j++) {
// Amount consumed by
// person j
int consume = (arr.get(j) * candies) / 100;
// Update the count of
// candies
candies -= consume;
}
}
// Check if person 1 gets the
// good share of candies
return (taken >= good_share);
}
// Function to find minimum value of
// K such that the first person gets
// at least (N/(M+1)) candies
static void minimumK(ArrayList<Integer> arr, int N,
int M)
{
// Find the minimum required value
// of candies for the first person
int good_share = (int)Math.ceil((N * 1.0)
/ ((M + 1) * 1.0));
int lo = 1, hi = N;
// Iterate until low is less
// than or equal to mid
while (lo < hi) {
// Find the value of mid
int mid = (lo + hi) / 2;
// Check for mid, whether it
// can be the possible value
// of K or not
if (check(mid, N, M, arr,
good_share)) {
// Update the value of hi
hi = mid;
}
// Otherwise, update the
// value of lo
else {
lo = mid + 1;
}
}
// Print the resultant minimum
// value of K
System.out.print(hi);
}
// Driver Code
public static void main(String[] args)
{
int N = 13, M = 1;
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(50);
minimumK(arr, N, M);
}
}
// This code is contributed by avijitmondal1998.
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ashutoshrathi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA