cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2014 · MediumLinear recurrence

Annual Sheep Population

National Olympiad — Municipal round (2014 season)

Submission name: sheeps.cpp

Solve in Editor →

Problem summary

Initially there is one mother sheep and her newborn female lamb. The mother gives birth annually; every female lamb starts giving birth at age three and then does so annually. Count all living sheep and lambs after k years.

Input

The number k of years.

Output

The total population after k years.

Constraints

4 ≤ k ≤ 112; all animals remain alive.

Worked example

Input and output for the worked example discussed below.

Input

4

Output

9

Solution analysis

  1. Let population[t] count all animals after year t, with the initial birth at t=0. The first totals are population[0]=2, population[1]=3, population[2]=4.
  2. At year t≥3, every animal already present at year t−3 is old enough to give birth now, while younger animals are not. Thus births at t equal population[t−3], and population[t]=population[t−1]+population[t−3].
  3. This gives 2,3,4,6,9,13,19,28,… . After four years there are 9 animals, matching the sample. Store totals in long long; the year-112 result is 7536815746437618530 and still fits.

Why it works

The mature mothers in year t are exactly the animals alive in year t−3: each is now at least three years old, and later-born lambs are too young. No animal dies, so adding one birth per mature mother to the previous population gives the recurrence. The initial three totals account for the original mother’s annual births.

Complexity: O(k) time and O(k) space for a transparent table; only three previous totals are needed for an O(1)-space variant.

Watch out. Do not use Fibonacci’s two-year recurrence. The original mother already reproduces at the start, unlike newborn lambs. int overflows long before the maximum year.

Commented C++17 solution

An independently written complete program with standard headers.

#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
    int years;
    cin>>years;
    vector<long long>population(max(years+1,3),0);
    population[0]=2;
    population[1]=3;
    population[2]=4;
    for(int year=3;year<=years;year++){
        // Every animal present three years earlier can now give birth.
        population[year]=population[year-1]+population[year-3];
    }
    cout<<population[years]<<'\n';
}

Source: Arena Olimpiici ↗