P4642 [BJWC2008] Equation

You are given $3 \times N$ positive integers: $A_1, A_2...A_n$ $B_1, B_2...B_n$ $C_1, C_2...C_n$ You are also given $M$ pairs of positive integers $S_i, T_i$. For each pair $S_i, T_i$, find a set of non-negative real solutions to the following system of equations: $A_1X_1 + A_2X_2 + ... + A_nX_n = S_i$ $B_1X_1 + B_2X_2 + ... + B_nX_n = T_i$ such that $C_1X_1 + C_2X_2 + ... + C_nX_n$ is maximized.

The first line contains two integers $N, M$. The next $N$ lines each contain three positive integers $A_i, B_i, C_i$. Constraints: $N \leq 10^5$, $M \leq 10^4$. $1 \le A_i, B_i, C_i, S_i, T_i \le 1000000$.

Output $M$ lines. The $i$-th line corresponds to $S_i, T_i$. If the system has no solution, output `IMPOSSIBLE`. Otherwise, output a real number rounded to five decimal places, representing the corresponding maximum value.

Translated by ChatGPT 5