以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

可复制的 PDF 提取文本
XIX Russia Team Open, High School Programming Contest
St Petersburg, Barnaul, Tbilisi, Almaty, Kremenchug, Sochi, December 9, 2018
Problem I. Minimal Product
Time limit: 2 seconds
Memory limit: 512 megabytes
You are given an array of integers a1, . . . , an. Find two indices i and j such that i < j, ai < aj, and the
product ai · aj is as small as possible.
Input
The input consists of several tests. The first line contains a single integer t — the number of tests
(1 ≤t ≤104). 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, b1,
b2 (2 ≤n ≤107, −2 · 109 ≤l ≤r ≤2 · 109, 0 ≤x, y, z, b1, b2 < 232), where n is the length of the array.
First, the sequence bi of length n is generated. Elements b1 and b2 are given. For i > 2 let
bi = (bi−2x + bi−1y + z) mod 232. For each i between 1 and n, ai = (bi mod (r −l + 1)) + l (thus,
−2 · 109 ≤ai ≤2 · 109).
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 · 107.
Output
For each test, print the smallest possible product ai · aj in a separate line. If there are no such i and j
that i < j and ai < aj, print “IMPOSSIBLE”.
Example
standard input standard output
2 -15
4 -5 5 11 13 17 0 3 IMPOSSIBLE
5 0 100 0 1 0 42 42
Note
Let us consider the generation of the array in the first test.
First, the sequence b is generated.
• b1 = 0
• b2 = 3
• b3 = (11 · 0 + 13 · 3 + 17) mod 232 = 56
• b4 = (11 · 3 + 13 · 56 + 17) mod 232 = 778
Then it is used to generate a.
• a1 = (0 mod (5 −(−5) + 1)) + (−5) = (0 mod 11) −5 = −5
• a2 = (3 mod 11) −5 = −2
• a3 = (56 mod 11) −5 = −4
• a4 = (778 mod 11) −5 = 3
Thus, a = [−5, −2, −4, 3]. The answer is −5 · 3 = −15.
In the second test the array is [42, 42, 42, 42, 42].
Page 13 of 18