19825번 - Minimal Product 다국어

You are given an array of integers $a_1,\dots,a_n$. Find two indices $i$ and $j$ such that $i<j$, $a_i<a_j$, and the product $a_i \cdot a_j$ is as small as possible.

The input consists of several tests. The first line contains a single integer $t$ --- the number of tests ($1 \leq t \leq 10^4$). Each of the following $t$ lines describes one test.

Each test is generated using the following algorithm. The test is described by integers $n$, $l$, $r$, $x$, $y$, $z$, $b_1$, $b_2$ ($2 \leq n \leq 10^7$, $-2\cdot10^9 \leq l \leq r \leq 2\cdot10^9$, $0 \leq x,y,z,b_1,b_2 < 2^{32}$), where $n$ is the length of the array.

First, the sequence $b_i$ of length $n$ is generated. Elements $b_1$ and $b_2$ are given. For $i>2$ let $b_i=(b_{i-2}x+b_{i-1}y+z) \bmod 2^{32}$. For each $i$ between $1$ and $n$, $a_i=(b_i \bmod (r - l + 1)) + l$ (thus, $-2\cdot10^9 \leq a_i \leq 2\cdot10^9$).

It is recommended to use 64-bit integers to generate the sequence to avoid integer overflow.

The sum of $n$ in all tests does not exceed $2 \cdot 10^7$.

For each test, print the smallest possible product $a_i \cdot a_j$ in a separate line. If there are no such $i$ and $j$ that $i<j$ and $a_i<a_j$, print "IMPOSSIBLE".

Let us consider the generation of the array in the first test.

First, the sequence $b$ is generated.

• $b_1 = 0$
• $b_2 = 3$
• $b_3 = (11\cdot 0 + 13\cdot 3 + 17)\bmod 2^{32}=56$
• $b_4 = (11\cdot 3 + 13\cdot 56 + 17)\bmod 2^{32}=778$

Then it is used to generate $a$.

• $a_1 = (0\bmod (5-(-5) + 1)) + (-5)=(0 \bmod 11) - 5 = -5$
• $a_2 = (3 \bmod 11) - 5 = -2$
• $a_3 = (56 \bmod 11) - 5 = -4$
• $a_4 = (778 \bmod 11) - 5 = 3$

Thus, $a = [-5,-2,-4,3]$. The answer is $-5 \cdot 3=-15$.

In the second test the array is $[42,42,42,42,42]$.