Análisis del problema

Se parte del escalón \(0\) y en cada paso se sube 1 o 2 escalones. Se pide contar de cuántas maneras distintas (el orden importa) se llega al escalón \(n\), para varios casos de prueba.

Idea de la solución

Sea \(f(n)\) el número de maneras de llegar al escalón \(n\). El último paso para llegar a \(n\) solo pudo ser de dos tipos:

• Venir del escalón \(n-1\) con un paso de 1 escalón: hay \(f(n-1)\) maneras.
• Venir del escalón \(n-2\) con un paso de 2 escalones: hay \(f(n-2)\) maneras.

Como estos dos casos son disjuntos y cubren todas las posibilidades:

\(f(n) = f(n-1) + f(n-2)\)

con los casos base:

• \(f(0) = 1\) (ya estás en el piso, una manera: no hacer nada).
• \(f(1) = 1\) (solo un paso de 1).

Esto es la sucesión de Fibonacci desplazada: \(1, 1, 2, 3, 5, 8, ...\)

Verificación con el ejemplo

Coincide con el ejemplo: \(f(1)=1\), \(f(2)=2\), \(f(4)=5\).

Sobre el tamaño de los números

Para \(n = 90\), \(f(90)\) es aproximadamente \(4.66 \times 10^{18}\), que es menor que \(2^{63}-1 \approx 9.22 \times 10^{18}\). Por lo tanto cabe en un long long (o unsigned long long) sin desbordamiento. Con \(n = 91\) todavía cabría, pero con \(n = 93\) ya no, así que el límite \(n \le 90\) está pensado para esto.

Estrategia

Se precalcula el arreglo f[0..90] una sola vez y cada consulta se responde en \(O(1)\).

Código en C++

#include <iostream>
using namespace std;

int main() {
    const int MAXN = 90;
    long long f[MAXN + 1];

    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i <= MAXN; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << f[n] << "\n";
    }

    return 0;
}

Explicación del código

1. long long f[MAXN + 1]: arreglo con los resultados para todos los \(n\) de \(0\) a \(90\). Se usa long long porque los valores llegan a \(10^{18}\).
2. f[0] = 1; f[1] = 1;: casos base.
3. El ciclo for aplica la recurrencia \(f(i) = f(i-1) + f(i-2)\) y llena toda la tabla.
4. Se lee \(t\) y, por cada caso, se lee \(n\) y se imprime f[n] directamente.

Complejidad

• Precálculo: \(O(M)\), con \(M = 90\).
• Consultas: \(O(t)\), una por caso.
• Total: \(O(M + t)\).
• Memoria: \(O(M)\).

Posibles errores comunes

Prueba con el ejemplo

Entrada

3
1
2
4

Salida

1
2
5