← 返回题目列表

Codeforces · 1090/I

I. 最小产品

中文机器翻译题面 查看原题

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

Minimal Product - 原题 PDF 第 1 页
原题PDF第13页
可复制的 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