P1011 [NOIP 1998 Senior] Station

A train departs from the origin (called station $1$). At the origin, $a$ people board. It then arrives at station $2$; at station $2$ some people board and alight, but the numbers boarding and alighting are equal, so when departing station $2$ (i.e., before arriving at station $3$), there remain $a$ people on the train. From station $3$ onward (including station $3$), the numbers boarding and alighting follow a rule: the number boarding at each station equals the sum of the numbers who boarded at the previous two stations, and the number alighting equals the number who boarded at the previous station. This holds through the penultimate station, station $n-1$. You are given that there are $n$ stations in total, $a$ people board at the origin, and at the last station the number of people alighting is $m$ (everyone gets off). Find the number of people on the train when departing station $x$.

A single line containing four integers: the number of people boarding at the origin $a$, the number of stations $n$, the number of people alighting at the terminal station $m$, and the station index to query $x$.

Output a single integer: the number of people on the train when departing station $x$.

For all test cases, $1 \leq a \leq 20$, $1 \leq x \leq n \leq 20$, $1 \leq m \leq 2 \times 10^4$. NOIP 1998 Senior Problem 1. Translated by ChatGPT 5