310430: CF1832D1. Red-Blue Operations (Easy Version)

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D1. Red-Blue Operations (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The only difference between easy and hard versions is the maximum values of $n$ and $q$.

You are given an array, consisting of $n$ integers. Initially, all elements are red.

You can apply the following operation to the array multiple times. During the $i$-th operation, you select an element of the array; then:

  • if the element is red, it increases by $i$ and becomes blue;
  • if the element is blue, it decreases by $i$ and becomes red.

The operations are numbered from $1$, i. e. during the first operation some element is changed by $1$ and so on.

You are asked $q$ queries of the following form:

  • given an integer $k$, what can the largest minimum in the array be if you apply exactly $k$ operations to it?

Note that the operations don't affect the array between queries, all queries are asked on the initial array $a$.

Input

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 1000$) — the number of elements in the array and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The third line contains $q$ integers $k_1, k_2, \dots, k_q$ ($1 \le k_j \le 10^9$).

Output

For each query, print a single integer — the largest minimum that the array can have after you apply exactly $k$ operations to it.

ExamplesInput
4 10
5 2 8 4
1 2 3 4 5 6 7 8 9 10
Output
3 4 5 6 7 8 8 10 8 12
Input
5 10
5 2 8 4 4
1 2 3 4 5 6 7 8 9 10
Output
3 4 5 6 7 8 9 8 11 8
Input
2 5
2 3
10 6 8 1 3
Output
10 7 8 3 3

Input

题意翻译

有一个长度为 $n$ 的序列 $a$ ,每个位置有一个颜色,初始全为红色。第 $i$ 次操作选择一个位置 $x$,如果为红色就把 $a_x$ 加 $i$ ,并变成蓝色,否则把 $a_x$ 减 $i$ ,并变成红色。 $q$ 次询问给定一个 $k$ ,求恰好 $k$ 次操作后 $a$ 序列最小值的最大值。

Output

题目大意:
这个题目分为简单和困难两个版本,唯一的区别在于n和q的最大值。你有一个由n个整数组成的数组,初始时所有元素都是红色的。你可以多次对数组执行以下操作:在第i次操作中,你选择数组中的一个元素,然后:如果该元素是红色的,它增加i并变为蓝色;如果该元素是蓝色的,它减少i并变为红色。操作从1开始编号,即在第一次操作中某个元素变化1,依此类推。你会被问q个查询,形式如下:给定一个整数k,如果你对数组执行恰好k次操作,数组的最小值最大可以是多少?注意,操作不会在查询之间影响数组,所有查询都是基于初始数组a。

输入数据格式:
第一行包含两个整数n和q(1≤n, q≤1000)——数组中元素的数量和查询的数量。
第二行包含n个整数a1, a2, …, an(1≤ai≤10^9)。
第三行包含q个整数k1, k2, …, kq(1≤kj≤10^9)。

输出数据格式:
对于每个查询,打印一个整数——在你对数组执行恰好k次操作后,数组的最小值最大可以是多少。

示例:
输入:
4 10
5 2 8 4
1 2 3 4 5 6 7 8 9 10

输出:
3 4 5 6 7 8 8 10 8 12

输入:
5 10
5 2 8 4 4
1 2 3 4 5 6 7 8 9 10

输出:
3 4 5 6 7 8 9 8 11 8

输入:
2 5
2 3
10 6 8 1 3

输出:
10 7 8 3 3题目大意: 这个题目分为简单和困难两个版本,唯一的区别在于n和q的最大值。你有一个由n个整数组成的数组,初始时所有元素都是红色的。你可以多次对数组执行以下操作:在第i次操作中,你选择数组中的一个元素,然后:如果该元素是红色的,它增加i并变为蓝色;如果该元素是蓝色的,它减少i并变为红色。操作从1开始编号,即在第一次操作中某个元素变化1,依此类推。你会被问q个查询,形式如下:给定一个整数k,如果你对数组执行恰好k次操作,数组的最小值最大可以是多少?注意,操作不会在查询之间影响数组,所有查询都是基于初始数组a。 输入数据格式: 第一行包含两个整数n和q(1≤n, q≤1000)——数组中元素的数量和查询的数量。 第二行包含n个整数a1, a2, …, an(1≤ai≤10^9)。 第三行包含q个整数k1, k2, …, kq(1≤kj≤10^9)。 输出数据格式: 对于每个查询,打印一个整数——在你对数组执行恰好k次操作后,数组的最小值最大可以是多少。 示例: 输入: 4 10 5 2 8 4 1 2 3 4 5 6 7 8 9 10 输出: 3 4 5 6 7 8 8 10 8 12 输入: 5 10 5 2 8 4 4 1 2 3 4 5 6 7 8 9 10 输出: 3 4 5 6 7 8 9 8 11 8 输入: 2 5 2 3 10 6 8 1 3 输出: 10 7 8 3 3

加入题单

上一题 下一题 算法标签: