Dadas N preguntas en un examen y K estudiantes en la clase. Del lote de estudiantes K, N estudiantes memorizaron exactamente una pregunta cada uno. Un correo puede contener un máximo de X preguntas.
Encuentre la cantidad mínima de correos necesarios para que toda la clase conozca todas las preguntas.
NOTA : Un correo tiene la siguiente información: Nombre del remitente, Nombre del destinatario y la(s) pregunta(s)
Ejemplos:
Entrada: N = 3, K = 3, X = 1
Salida: 6 El
estudiante 1 envía su pregunta al estudiante 2 y al estudiante 3 (2 correos),
también lo hacen el estudiante 2 y el estudiante 3, por lo que el total de correos = 2 * 3 = 6Entrada: N = 4, K = 9, X = 2
Salida: 19
Consulte el siguiente diagrama de flujo
Diagrama de flujo:
N = 4, K = 9, X = 2
Pivote = 4º estudiante
Los estudiantes 1, 2 y 3 envían 3 correos electrónicos al estudiante 4. Ahora el estudiante 4 tiene todas las preguntas. Los distribuye en consecuencia, 3/2 = 2 (usando ceil) correos a cada 3 estudiantes que ya tienen 1 pregunta y 4/2 = 2 correos para el resto de 5 estudiantes. Entonces el total de correos es (3 + 2 * 3 + 2 * 5) = 19
Enfoque: Aquí se ha utilizado un enfoque codicioso. Se selecciona un pivote que recibe todas las preguntas primero y luego las distribuye en consecuencia. Esto requerirá un número mínimo de pasos. Alumnos N-1, enviar cada una de sus preguntas al alumno N. Entonces, el estudiante N tiene todas las preguntas (correos enviados hasta ahora = N-1). Ahora se menciona que los correos contienen el nombre de los remitentes, por lo que el N-ésimo estudiante sabe qué pregunta proviene de quién, por lo que puede evitar devolver la misma pregunta. Ahora el estudiante enésimo actúa como distribuidor, empaqueta las preguntas y las envía en consecuencia. Cada uno de los estudiantes N-1 necesita saber sobre el resto de las preguntas N-1. Entonces, el mínimo de correos que deben enviarse a cada uno de ellos es ceil ((N-1)/X), donde X es el número máximo de preguntas que puede contener un correo yceil denota la función de menor número entero. Así que el total de correos enviados hasta ahora = ceil ((N-1)/X) * (N-1) + (N-1). Entonces N estudiantes conocen todas las preguntas. El resto de los estudiantes de KN necesita conocer todas las N preguntas, por lo que cada uno de ellos debe recibir al menos correos electrónicos ceil (N/X), donde X es el número máximo de preguntas que puede contener un correo electrónico y ceil denota la función de número entero mínimo. Así que el correo total recibido es:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to find the
// minimum number of mails
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// Function returns the min no of mails required
long long int MinimumMail(int n, int k, int x)
{
// Using the formula derived above
ll m = (n - 1) + (ll)ceil((n - 1) * 1.0 / x) * (n - 1)
+ (ll)ceil(n * 1.0 / x) * (k - n);
return m;
}
// Driver Code
int main()
{
// no of questions
int N = 4;
// no of students
int K = 9;
// maximum no of questions a mail can hold
int X = 2;
// Calling function
cout << MinimumMail(N, K, X) << endl;
return 0;
}
Java
// Java code to find the
// minimum number of mails
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG
{
// Function returns the min
// no of mails required
static double MinimumMail(int n,
int k,
int x)
{
// Using the formula
// derived above
double m = (n - 1) + Math.ceil((n - 1) * 1.0 / x) * (n - 1)
+ Math.ceil(n * 1.0 / x) * (k - n);
return m;
}
// Driver Code
public static void main(String[] args)
{
// no of questions
int N = 4;
// no of students
int K = 9;
// maximum no of questions
// a mail can hold
int X = 2;
// Calling function
System.out.print((int)MinimumMail(N, K, X) + "\n");
}
}
Python3
# Python3 code to find the minimum # number of mails import math # Function returns the min no of # mails required def MinimumMail(n, k, x): # Using the formula derived above m = ((n - 1) + int(math.ceil((n - 1) * 1.0 / x) * (n - 1) + math.ceil(n * 1.0 / x) * (k - n))); return m; # Driver Code # no of questions N = 4; # no of students K = 9; # maximum no of questions # a mail can hold X = 2; # Calling function print(MinimumMail(N, K, X)); # This code is contributed by mits
C#
// C# code to find the
// minimum number of mails
using System;
class GFG
{
// Function returns the min
// no of mails required
static double MinimumMail(int n,
int k,
int x)
{
// Using the formula
// derived above
double m = (n - 1) + Math.Ceiling((n - 1) *
1.0 / x) * (n - 1) +
Math.Ceiling(n * 1.0 /
x) * (k - n);
return m;
}
// Driver Code
public static void Main()
{
// no of questions
int N = 4;
// no of students
int K = 9;
// maximum no of questions
// a mail can hold
int X = 2;
// Calling function
Console.WriteLine((int)MinimumMail(N, K, X) + "\n");
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP code to find the
// minimum number of mails
// Function returns the
// min no of mails required
function MinimumMail($n, $k, $x)
{
// Using the formula
// derived above
$m = ($n - 1) + ceil(($n - 1) *
1.0 / $x) * ($n - 1) +
ceil($n * 1.0 /
$x) * ($k - $n);
return $m;
}
// Driver Code
// no of questions
$N = 4;
// no of students
$K = 9;
// maximum no of questions
// a mail can hold
$X = 2;
// Calling function
echo MinimumMail($N, $K, $X), "\n";
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript code to find the minimum
// number of mails
// Function returns the min
// no of mails required
function MinimumMail(n, k, x)
{
// Using the formula
// derived above
let m = (n - 1) + Math.ceil((n - 1) * 1.0 / x) *
(n - 1) + Math.ceil(n * 1.0 / x) * (k - n);
return m;
}
// Driver code
// No of questions
let N = 4;
// No of students
let K = 9;
// Maximum no of questions
// a mail can hold
let X = 2;
// Calling function
document.write(MinimumMail(N, K, X) + "</br>");
// This code is contributed by divyesh072019
</script>
19
Publicación traducida automáticamente
Artículo escrito por agnivakolay y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA