Mistrz Programowania

Mistrz Programowania 2025 runda 4 poziom b
Tagi: matematyka programowanie dynamiczne
Autor zadania: Daniel Olkowski Autor omówienia: Tomasz Kwiatkowski
Treść

Omówienie zadania Puk

Możemy iteracyjnie obliczyć kolejne wartości ciągu $A$ utrzymując je w tablicy i obliczając kolejne wartości na podstawie poprzednich.

Przykładowe implementacje

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> A(max(2, n));
    A[0] = A[1] = 1;
    for (int i = 2; i < n; ++i) {
        A[i] = A[i - A[i - 1]] + A[i - A[i - 2]];
    }
    cout << A.back() << endl;
    return 0;
}

Python

def main():
    n = int(input())
    A = [0] * max(2, n)
    A[0] = A[1] = 1
    for i in range(2, n):
        A[i] = A[i - A[i - 1]] + A[i - A[i - 2]]
    print(A[-1])


main()

Uwagi