Задача №114485. Минимальное произведение
Задан массив целых чисел \(a_1,\dots,a_n\). Требуется найти такие \(i\) и \(j\), что \(i<j\), \(a_i<a_j\), и произведение \(a_i \cdot a_j\) минимальное возможное.
Входные данные содержат один или несколько тестов. В первой строке задано целое число \(t\) — количество тестов (\(1 \leq t \leq 10^4\)). Каждая из следующих \(t\) строк задаёт один тест.
Каждый тест генерируется по следующему алгоритму. Тест задаётся целыми числами \(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}\)). Число \(n\) задаёт длину массива.
Сначала генерируется последовательность \(b_i\) длины \(n\), \(b_1\) и \(b_2\) заданы, а для \(i>2\) \(b_i=(b_{i-2}x+b_{i-1}y+z) \bmod 2^{32}\). Затем для всех \(i\) от \(1\) до \(n\) присваивается \(a_i=(b_i \bmod (r - l + 1)) + l\) (таким образом, \(-2\cdot10^9 \leq a_i \leq 2\cdot10^9\)).
Обратите внимание, что при генерации последовательности следует опасаться переполнения целочисленных типов, рекомендуется использовать 64-битный тип данных.
Сумма \(n\) по всем тестам не превосходит \(2 \cdot 10^7\).
Для каждого теста выведите в отдельной строке минимально возможное значение \(a_i \cdot a_j\). Если не существует таких \(i\) и \(j\), что \(i<j\) и \(a_i<a_j\), выведите « IMPOSSIBLE ».
Рассмотрим подробнее генерацию массива в первом тесте.
Сначала генерируется массив \(b\).
- \(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\).
Теперь по нему генерируется массив \(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\).
Таким образом, заданный массив \(a = [-5,-2,-4,3]\). Ответ равен \(-5 \cdot 3=-15\).
Во втором тесте массив имеет вид \([42,42,42,42,42]\).
2 4 -5 5 11 13 17 0 3 5 0 100 0 1 0 42 42
-15 IMPOSSIBLE