Dado que un zoológico tiene un solo pollito. Un pollito da a luz a 2 pollitos todos los días y la esperanza de vida de un pollito es de 6 días. La tarea es encontrar el número de pollitos en el día N.
Ejemplos:
Entrada: N = 3
Salida: 9
Primer día: 1 pollito
Segundo día: 1 + 2 = 3
Tercer día: 3 + 6 = 9
Entrada: N = 12
Salida: 173988
Enfoque simple: se da que la esperanza de vida de un pollito es de 6 días, por lo que ningún pollito muere hasta el sexto día. La población diaria del día actual será 3 veces la del día anterior. Una cosa más es tener en cuenta que el pollito nacido el iésimo día no se cuenta en ese día, se contará en el día siguiente y los cambios comienzan a partir del séptimo día. Entonces, el cálculo principal comienza a partir del séptimo día.
En el Séptimo Día: Los pollitos del 1er día mueren, por lo que según el cálculo manual serán 726.
En el Octavo Día:Dos pollitos recién nacidos nacidos el (8-6), es decir, el segundo día, mueren. Esto afectará a la población actual en 2/3. Esta población debe deducirse de la población del día anterior porque hoy, es decir, el octavo día nacerán más recién nacidos, por lo que no podemos deducir directamente de la población de hoy. Esto luego se multiplicará por tres debido a los recién nacidos nacidos ese día.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// Function to return the number
// of chicks on the nth day
ll getChicks(int n)
{
// Size of dp[] has to be
// at least 6 (1-based indexing)
int size = max(n, 7);
ll dp[size];
dp[0] = 0;
dp[1] = 1;
// Every day current population
// will be three times of the previous day
for (int i = 2; i <= 6; i++) {
dp[i] = dp[i - 1] * 3;
}
// Manually calculated value
dp[7] = 726;
// From 8th day onwards
for (int i = 8; i <= n; i++) {
// Chick population decreases by 2/3 everyday.
// For 8th day on [i-6] i.e 2nd day population
// was 3 and so 2 new born die on the 6th day
// and so on for the upcoming days
dp[i] = (dp[i - 1] - (2 * dp[i - 6] / 3)) * 3;
}
return dp[n];
}
// Driver code
int main()
{
int n = 3;
cout << getChicks(n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
public class GFG {
// Function to return the number
// of chicks on the nth day
static long getChicks(int n)
{
// Size of dp[] has to be
// at least 6 (1-based indexing)
int size = Math.max(n, 7);
long []dp = new long[size];
dp[0] = 0;
dp[1] = 1;
// Every day current population
// will be three times of the previous day
for (int i = 2; i < 6; i++) {
dp[i] = dp[i - 1] * 3;
}
// Manually calculated value
dp[6] = 726;
// From 8th day onwards
for (int i = 8; i <= n; i++) {
// Chick population decreases by 2/3 everyday.
// For 8th day on [i-6] i.e 2nd day population
// was 3 and so 2 new born die on the 6th day
// and so on for the upcoming days
dp[i] = (dp[i - 1] - (2 * dp[i - 6] / 3)) * 3;
}
return dp[n];
}
// Driver code
public static void main(String[] args) {
int n = 3;
System.out.println(getChicks(n));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python implementation of the approach # Function to return the number # of chicks on the nth day def getChicks(n): # Size of dp[] has to be # at least 6 (1-based indexing) size = max(n, 7); dp = [0]*size; dp[0] = 0; dp[1] = 1; # Every day current population # will be three times of the previous day for i in range(2,7): dp[i] = dp[i - 1] * 3; # Manually calculated value dp[6] = 726; # From 8th day onwards for i in range(8,n+1): # Chick population decreases by 2/3 everyday. # For 8th day on [i-6] i.e 2nd day population # was 3 and so 2 new born die on the 6th day # and so on for the upcoming days dp[i] = (dp[i - 1] - (2 * dp[i - 6] // 3)) * 3; return dp[n]; # Driver code n = 3; print(getChicks(n)); # This code is contributed by Princi Singh
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the number
// of chicks on the nth day
static long getChicks(int n)
{
// Size of dp[] has to be
// at least 6 (1-based indexing)
int size = Math.Max(n, 7);
long []dp = new long[size];
dp[0] = 0;
dp[1] = 1;
// Every day current population
// will be three times of the previous day
for (int i = 2; i < 6; i++)
{
dp[i] = dp[i - 1] * 3;
}
// Manually calculated value
dp[6] = 726;
// From 8th day onwards
for (int i = 8; i <= n; i++)
{
// Chick population decreases by 2/3 everyday.
// For 8th day on [i-6] i.e 2nd day population
// was 3 and so 2 new born die on the 6th day
// and so on for the upcoming days
dp[i] = (dp[i - 1] - (2 * dp[i - 6] / 3)) * 3;
}
return dp[n];
}
// Driver code
static public void Main ()
{
int n = 3;
Console.WriteLine(getChicks(n));
}
}
// This code has been contributed by @Tushil..
Javascript
<script>
// Javascript implementation of the approach
// Function to return the number
// of chicks on the nth day
function getChicks(n)
{
// Size of dp[] has to be
// at least 6 (1-based indexing)
let size = Math.max(n, 7);
let dp = new Array(size);
dp.fill(0);
dp[0] = 0;
dp[1] = 1;
// Every day current population
// will be three times of the previous day
for (let i = 2; i < 6; i++)
{
dp[i] = dp[i - 1] * 3;
}
// Manually calculated value
dp[6] = 726;
// From 8th day onwards
for (let i = 8; i <= n; i++)
{
// Chick population decreases by 2/3 everyday.
// For 8th day on [i-6] i.e 2nd day population
// was 3 and so 2 new born die on the 6th day
// and so on for the upcoming days
dp[i] = (dp[i - 1] -
(2 * parseInt(dp[i - 6] / 3, 10))) * 3;
}
return dp[n];
}
let n = 3;
document.write(getChicks(n));
</script>
9
Enfoque eficiente: si observa de cerca, puede observar un patrón que es una cantidad de pollitos para el día N en el zoológico que se puede calcular directamente usando la fórmula pow (3, N – 1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// Function to return the number
// of chicks on the nth day
ll getChicks(int n)
{
ll chicks = (ll)pow(3, n - 1);
return chicks;
}
// Driver code
int main()
{
int n = 3;
cout << getChicks(n);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG
{
// Function to return the number
// of chicks on the nth day
static int getChicks(int n)
{
int chicks = (int)Math.pow(3, n - 1);
return chicks;
}
// Driver code
public static void main (String[] args)
{
int n = 3;
System.out.println (getChicks(n));
}
}
// This code is contributed by Tushil.
Python 3
# Python 3 implementation of the approach # Function to return the number # of chicks on the nth day def getChicks( n): chicks = pow(3, n - 1) return chicks # Driver code if __name__ == "__main__": n = 3 print ( getChicks(n)) # This code is contributed by ChitraNayal
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the number
// of chicks on the nth day
static int getChicks(int n)
{
int chicks = (int)Math.Pow(3, n - 1);
return chicks;
}
// Driver code
public static void Main()
{
int n = 3;
Console.WriteLine(getChicks(n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function to return the number
// of chicks on the nth day
function getChicks(n)
{
let chicks = Math.pow(3, n - 1);
return chicks;
}
let n = 3;
document.write(getChicks(n));
</script>
9