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;
}

 

全部评论

相关推荐

沉淀一会:**圣经 1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务