Dados dos números enteros N y M que denotan el número de personas de Tipo1 y Tipo2 respectivamente. La tarea es encontrar el número máximo de equipos que se pueden formar con estos dos tipos de personas. Un equipo puede contener 2 personas de Tipo1 y 1 persona de Tipo2 o 1 persona de Tipo1 y 2 personas de Tipo2 .
Ejemplos:
Entrada: N = 2, M = 6
Salida: 2
(Tipo1, Tipo2, Tipo2) y (Tipo1, Tipo2, Tipo2) son los dos equipos posibles.
Entrada: N = 4, M = 5
Salida: 3
Enfoque: un enfoque codicioso es elegir 2 personas del grupo que tiene más miembros y 1 persona del grupo con menos miembros y actualizar el recuento de personas en cada uno de los grupos en consecuencia. La condición de terminación será cuando no se puedan formar más equipos.
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 that returns true if it possible
// to form a team with the given n and m
bool canFormTeam(int n, int m)
{
// 1 person of Type1 and 2 persons of Type2
// can be chosen
if (n >= 1 && m >= 2)
return true;
// 1 person of Type2 and 2 persons of Type1
// can be chosen
if (m >= 1 && n >= 2)
return true;
// Cannot from a team
return false;
}
// Function to return the maximum number of teams
// that can be formed
int maxTeams(int n, int m)
{
// To store the required count of teams formed
int count = 0;
while (canFormTeam(n, m)) {
if (n > m) {
// Choose 2 persons of Type1
n -= 2;
// And 1 person of Type2
m -= 1;
}
else {
// Choose 2 persons of Type2
m -= 2;
// And 1 person of Type1
n -= 1;
}
// Another team has been formed
count++;
}
return count;
}
// Driver code
int main()
{
int n = 4, m = 5;
cout << maxTeams(n, m);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function that returns true
// if it possible to form a
// team with the given n and m
static boolean canFormTeam(int n, int m)
{
// 1 person of Type1 and 2 persons
// of Type2 can be chosen
if (n >= 1 && m >= 2)
return true;
// 1 person of Type2 and 2 persons
// of Type1 can be chosen
if (m >= 1 && n >= 2)
return true;
// Cannot from a team
return false;
}
// Function to return the maximum
// number of teams that can be formed
static int maxTeams(int n, int m)
{
// To store the required count
// of teams formed
int count = 0;
while (canFormTeam(n, m))
{
if (n > m)
{
// Choose 2 persons of Type1
n -= 2;
// And 1 person of Type2
m -= 1;
}
else
{
// Choose 2 persons of Type2
m -= 2;
// And 1 person of Type1
n -= 1;
}
// Another team has been formed
count++;
}
return count;
}
// Driver code
public static void main(String args[])
{
int n = 4, m = 5;
System.out.println(maxTeams(n, m));
}
}
// This code is contributed by Ryuga
Python3
# Python 3 implementation of the approach # Function that returns true if it possible # to form a team with the given n and m def canFormTeam(n, m): # 1 person of Type1 and 2 persons of Type2 # can be chosen if (n >= 1 and m >= 2): return True # 1 person of Type2 and 2 persons of Type1 # can be chosen if (m >= 1 and n >= 2): return True # Cannot from a team return False # Function to return the maximum number of teams # that can be formed def maxTeams(n, m): # To store the required count of teams formed count = 0 while (canFormTeam(n, m)): if (n > m): # Choose 2 persons of Type1 n -= 2 # And 1 person of Type2 m -= 1 else: # Choose 2 persons of Type2 m -= 2 # And 1 person of Type1 n -= 1 # Another team has been formed count += 1 return count # Driver code if __name__ == '__main__': n = 4 m = 5 print(maxTeams(n, m)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true if it possible
// to form a team with the given n and m
static bool canFormTeam(int n, int m)
{
// 1 person of Type1 and 2 persons
// of Type2 can be chosen
if (n >= 1 && m >= 2)
return true;
// 1 person of Type2 and 2 persons
// of Type1 can be chosen
if (m >= 1 && n >= 2)
return true;
// Cannot from a team
return false;
}
// Function to return the maximum
// number of teams that can be formed
static int maxTeams(int n, int m)
{
// To store the required count
// of teams formed
int count = 0;
while (canFormTeam(n, m))
{
if (n > m)
{
// Choose 2 persons of Type1
n -= 2;
// And 1 person of Type2
m -= 1;
}
else
{
// Choose 2 persons of Type2
m -= 2;
// And 1 person of Type1
n -= 1;
}
// Another team has been formed
count++;
}
return count;
}
// Driver code
public static void Main()
{
int n = 4, m = 5;
Console.WriteLine(maxTeams(n, m));
}
}
// This code is contributed by
// tufan_gupta2000
PHP
<?php
// PHP implementation of the approach
// Function that returns true if it possible
// to form a team with the given n and m
function canFormTeam($n, $m)
{
// 1 person of Type1 and 2 persons
// of Type2 can be chosen
if ($n >= 1 && $m >= 2)
return true;
// 1 person of Type2 and 2 persons
// of Type1 can be chosen
if ($m >= 1 && $n >= 2)
return true;
// Cannot from a team
return false;
}
// Function to return the maximum number
// of teams that can be formed
function maxTeams($n, $m)
{
// To store the required count
// of teams formed
$count = 0;
while (canFormTeam($n, $m))
{
if ($n > $m)
{
// Choose 2 persons of Type1
$n -= 2;
// And 1 person of Type2
$m -= 1;
}
else
{
// Choose 2 persons of Type2
$m -= 2;
// And 1 person of Type1
$n -= 1;
}
// Another team has been formed
$count++;
}
return $count;
}
// Driver code
$n = 4;
$m = 5;
echo maxTeams($n, $m);
// This code is contributed by mits
?>
Javascript
<script>
// javascript implementation of the approach
// Function that returns true
// if it possible to form a
// team with the given n and m
function canFormTeam(n, m)
{
// 1 person of Type1 and 2 persons
// of Type2 can be chosen
if (n >= 1 && m >= 2)
return true;
// 1 person of Type2 and 2 persons
// of Type1 can be chosen
if (m >= 1 && n >= 2)
return true;
// Cannot from a team
return false;
}
// Function to return the maximum
// number of teams that can be formed
function maxTeams(n , m)
{
// To store the required count
// of teams formed
var count = 0;
while (canFormTeam(n, m))
{
if (n > m)
{
// Choose 2 persons of Type1
n -= 2;
// And 1 person of Type2
m -= 1;
}
else
{
// Choose 2 persons of Type2
m -= 2;
// And 1 person of Type1
n -= 1;
}
// Another team has been formed
count++;
}
return count;
}
// Driver code
var n = 4, m = 5;
document.write(maxTeams(n, m));
// This code is contributed by todaysgaurav
</script>
Producción:
3
Complejidad del tiempo: O(min(n, m))
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA