ICPC Asia Taipei-Hsinchu Regional 2019 The League of Sequence Designers（构造）

Problem Description

Consider the following sequence problem: given nn integers a_{1}, a_{2}, \ldots, a_{n},a1​,a2​,…,an​, where \left|a_{i}\right| \leq 10^{6}∣ai​∣≤106for all 1 \leq i \leq n1≤i≤n and 1 \leq n<2000,1≤n<2000,compute

\max _{1 \leq \ell \leq r \leq n}(r-\ell+1) \cdot \sum_{\ell \leq i \leq r} a_{i}max1≤ℓ≤r≤n​(r−ℓ+1)⋅∑ℓ≤i≤r​ai​

As an attempt to solve the above problem, Natasha came up with a textbook greedy algorithm using the idea of computing heaviest segment via prefix sums as follows:

As you can see, Natasha's idea is not entirely correct. For example, when the input sequence is 6,-8,7,-42,6,−8,7,−42, the function FindAnswer will return 7,7, but the correct answer is 3 \cdot(6-8+7)=153⋅(6−8+7)=15

Bruce tries to tell Natasha that her solution is not correct, but she does not believe.

Given an integer kk and a lower bound of sequence length LL, your task in this problem is to help Bruce design a sequence of nn integers with n \geq Ln≥L such that the correct answer and the answer produced by Natasha's algorithm differ by exactly kk

Note that, the sequence you produce must follow the specification to the original problem. That is, 1 \leq n<20001≤n<2000 and \left|a_{i}\right| \leq 10^{6}∣ai​∣≤106 for all 1 \leq i \leq n .1≤i≤n. Print -1−1 if it is impossible to form such a sequence.

Input Format

The input file starts with an integer TT, the number of testcases, in the first line.

Then there are TT lines, one for each testcase, each containing two integers kk and LL, separated by a space.

Output Format

The output for each testcase consists of either one or two lines, depending on the result. The format is as follows.

If there exists no such sequences, print the integer -1−1 in a line. Otherwise, print in the first line the integer nn denoting the length of the sequence. In the second line, print the nnintegers a_{1}, \ldots, a_{n}a1​,…,an​ separated with a space.

Technical Specification

• 1 \leq T \leq 51≤T≤5
• 1 \leq k \leq 10^{9}1≤k≤109
• 0 \leq L \leq 10^{9}0≤L≤109

本题答案不唯一，符合要求的答案均正确

样例输入复制

3
8 3
612 7
4 2019

样例输出复制

4
6 -8 7 -42
7
30 -12 -99 123 -2 245  -300
-1

题意：

构造一个数列，使得给出的程序返回的结果与正确结果正好相差 k 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int N = 2e3 + 10;

int a[N];

int main()
{
    int k, l, t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &k, &l);
        if(l >= 2000)
        {
            cout<<-1<<'\n';
            continue;
        }
        int n = 1999;
        a[1] = -1;
        int tmp = 1999 + k;
        for(int i = 2; i < n; ++i)
        {
            a[i] = tmp / 1998;    //匀开
        }
        a[n] = tmp % 1998 + tmp / 1998;
        cout<<n<<'\n';
        for(int i = 1; i <= n; ++i)
        {
            cout<<a[i];
            if(i < n)
                cout<<'\n';
        }
    }
    return 0;
}