ZeroJudge B229: Route Problem

Consider constructing a path of length N on the integer lattice points in the X-Y plane. From a lattice point (x, y), the path can move right to the lattice point (x+1, y); or move left to the lattice point (x-1, y); or move up to the lattice point (x, y+1). A path of length N must pass through N distinct edges. How many paths of length N, starting from the origin (0, 0) and following the above rules, can be formed?

Sample Inputs/Outputs

Thought Process

To calculate the answer to this problem, use unsigned long long int. Declare an array ans to build the table, and initialize the first four positions with the values 0, 3, 7, and 17. Then, run a for loop from 4 to 50, and set ans[current_position] to ans[current_position-1] * 2 + ans[current_position-2].

Sample Code－ZeroJudge B229: Route Problem

#include <iostream>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    unsigned long long int N, ans[100] = {};
    ans[0] = 0;
    ans[1] = 3;
    ans[2] = 7;
    ans[3] = 17;
    for (int i = 4; i<=50; i++) {
        ans[i] = ans[i-1] * 2 + ans[i-2];
    }
    while (cin >> N) {
        cout << ans[N] << "\n";
    }
}

//ZeroJudge B229
//Dr. SeanXD