P8584 Explore the Unknown

Attached file:

In the year 2102, humans have built an interstellar passage from Earth to the Virgo $\alpha$ star. The passage stretches for hundreds of light-years. There are many signposts along the passage. The $i$-th signpost shows a fraction $\dfrac{a_i}{b_i}$ and a fraction operator $+$ or $-$. At the beginning, you are holding the number $0$. You walk backward along the passage. Each time you reach a signpost, **you use the number in your hand and the fraction on the signpost, apply the operator on the signpost to compute a new number, and then hold this new number (discarding the old one)**. Note that if the computed number is not an integer, it will be kept as a reduced fraction; otherwise, it will be kept as an integer. Now you want to know what number you will be holding when you reach the end of the passage.

The first line contains one positive integer $n$, indicating that there are $n$ signposts in the passage. Lines $2$ to $n+1$ each contain three positive integers $a_i, b_i, opt_i$, meaning that the fraction on the $i$-th signpost is $\dfrac{a_i}{b_i}$ and the operator is $opt_i$. Here, the two operations $+$ and $-$ are represented by $1$ and $2$, respectively.

Output one number in a single line. If the final result can be kept as an integer, output an integer $ans$ as the result. Otherwise, if the final result must be kept as a fraction, output a reduced fraction $\dfrac{a}{b}$ in the form `a/b`. You must ensure that $\dfrac{a}{b}$ is in lowest terms, i.e. $\gcd(a,b)=1$. Note that the result may be negative, and in that case you must keep the minus sign. For example, if the result is $-\dfrac{11451}{4}$, you should output `-11451/4`.

For $20\%$ of the testdata, the operator is only addition. For another $20\%$ of the testdata, the operator is only subtraction. For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^3$, $0 \leq a \leq 1000$, $0 < b \leq 1000$, and the answer and all intermediate values (integer part / numerator / denominator) do not exceed $2 \times 10^9$. Translated by ChatGPT 5