Since they are two choices for each jump, there are \(2^N\) ways of jumping in total. If we enumerate all these ways, it won’t finish in the time limit.

Here, note the following two facts.

• If multiple ways end up with the same coordinate, they can be considered the same
• Once the coordinate exceeds \(X\), it does no longer need to be considered

Therefore, we can consider the following Dynamic Programming (DP).

• \(\mathrm{dp}[i][j] : \) \(1\) if it is possible to reach coordinate \(j\) after \(i\) jumps, and otherwise \(0\)

We have to consider \(i\) between \(0\) and \(N\), and \(j\) between \(0\) and \(X\) (both inclusive), so the number of states is \(O(NX)\).

Process in the increasing order of \(i\). First, \(\mathrm{dp}[0][0] = 1\) and \(\mathrm{dp}[0][x] = 0 \, (x \gt 0)\). When we have calculated up to \(i = k\), we can obtain for \(i = k + 1\) as follows:

• For all \(j\), initialize as \(\mathrm{dp}[k + 1][j] := 0\).
• For all \(j\) such that \(\mathrm{dp}[k][j] = 1\), do the following. Here, \(a_k\) and \(b_k\) are \(0\)-indexed.
  • If \(j + a_k \leq X\), let \(\mathrm{dp}[k + 1][j + a_k] := 1\).
  • If \(j + b_k \leq X\), let \(\mathrm{dp}[k + 1][j + b_k] := 1\).

The answer can be determined by whether \(dp[N][X]\) is \(1\) or not. The complexity is \(O(NX)\).

Here is a figure corresponding to Sample Input 1.

Sample code (C++)

The solution above can be implemented so that the complexity becomes \(\displaystyle O\left(N + \frac{NX}{\sigma} \right)\). In C++, we can use std::bitset (Reference); in Python, we can directly use bigint.

Sample code (Python)