Insect Population Growth Problem

Time Limit: C/C++ 1000ms, Other Languages 2000ms
Memory Limit: C/C++ 256MB, Other Languages 512MB

Problem Description

Scientists in a tropical forest have discovered a special insect species with remarkable reproductive capabilities. Each pair of adult insects produces y pairs of eggs after x months. Each pair of eggs takes exactly two months to mature into adult insects. Assumign no adult insects die, and starting with one pair of adults in the first month, we need to determine the total number of adult insect pairs after Z months. Note that newly matured insects do not reproduce in their first month but start reproducing after X months.

Constraints: 1 ≤ X ≤ 20, 1 ≤ Y ≤ 20, X ≤ Z ≤ 50

Input

Three integers: x, y, and z

Output

The total number of adult insect pairs after Z months

Example 1

Input:
1 2 8

Output:
37

Example 2

Input:
5 13 39

Output:
847289

Sample Explanation for "1 2 8"

First reproduction occurs in month 2, producing 2 pairs of eggs. From then on, reproduction happens monthly.

Solution Approaches

1. Recursive Depth-First Search Approach

This approach models the reproduction process using recursion to track when each insect pair will reproduce.

#include <iostream>
using namespace std;

long long population[55];  // Stores population at each month
int reproductionDelay, offspringPairs, totalMonths;

void calculatePopulation(int currentMonth, long long currentPairs) {
    population[currentMonth] += currentPairs;
    
    // Calculate when this group will reproduce next
    int reproductionMonth = currentMonth + reproductionDelay + 2;
    
    // If reproduction happens within the time frame
    if (reproductionMonth <= totalMonths + 1) {
        // Each pair produces 'offspringPairs' new pairs
        calculatePopulation(reproductionMonth, currentPairs * offspringPairs);
    }
}

int main() {
    cin >> reproductionDelay >> offspringPairs >> totalMonths;
    
    // Start with one pair in month 1
    calculatePopulation(1, 1);
    
    // Sum up all adult pairs over the months
    long long totalAdults = 0;
    for (int i = 1; i <= totalMonths + 1; i++) {
        totalAdults += population[i];
    }
    
    cout << totalAdults << endl;
    return 0;
}
</iostream>

2. Dynamic Programming Approach

This solution uses dynamic programming to efficiently track the population by maintaining separate arrays for different age groups of insects.

#include <iostream>
using namespace std;

#define MAX_MONTHS 55

int main() {
    int maturationTime, offspringRate, duration;
    cin >> maturationTime >> offspringRate >> duration;
    
    // Three arrays to track insects at different stages:
    // 0: newly matured, 1: maturing, 2: ready to reproduce
    long long insects[3][MAX_MONTHS] = {0};
    long long monthlyNew[MAX_MONTHS] = {0};
    
    // Initial conditions: one pair in month 1
    insects[2][1] = 1;
    insects[1][1] = maturationTime;
    
    for (int month = 1; month <= duration; month++) {
        // Shift the maturation timeline
        monthlyNew[0] = monthlyNew[1];
        monthlyNew[1] = monthlyNew[2];
        monthlyNew[2] = 0;
        
        // Process each group of insects
        for (int group = 1; group <= MAX_MONTHS; group++) {
            insects[1][group]--;
            
            if (insects[1][group] == 0) {
                // This group is ready to reproduce
                monthlyNew[2] += insects[2][group] * offspringRate;
                insects[1][group] = maturationTime;
            }
        }
        
        // Add newly matured insects to the population
        if (monthlyNew[0] > 0) {
            insects[2][month] += monthlyNew[0];
            insects[1][month] = maturationTime;
        }
    }
    
    // Calculate total adult pairs
    long long totalAdults = 0;
    for (int i = 1; i <= duration; i++) {
        totalAdults += insects[2][i];
    }
    
    cout << totalAdults << endl;
    return 0;
}
</iostream>